@article{13988,
  abstract     = {Most permissionless blockchains inherently suffer from throughput limitations. Layer-2 systems, such as side-chains or Rollups, have been proposed as a possible strategy to overcome this limitation. Layer-2 systems interact with the main-chain in two ways. First, users can move funds from/to the main-chain to/from the layer-2. Second, layer-2 systems periodically synchronize with the main-chain to keep some form of log of their activity on the main-chain - this log is key for security. Due to this interaction with the main-chain, which is necessary and recurrent, layer-2 systems impose some load on the main-chain. The impact of such load on the main-chain has been, so far, poorly understood. In addition to that, layer-2 approaches typically sacrifice decentralization and security in favor of higher throughput. This paper presents an experimental study that analyzes the current state of Ethereum layer-2 projects. Our goal is to assess the load they impose on Ethereum and to understand their scalability potential in the long-run. Our analysis shows that the impact of any given layer-2 on the main-chain is the result of both technical aspects (how state is logged on the main-chain) and user behavior (how often users decide to transfer funds between the layer-2 and the main-chain). Based on our observations, we infer that without efficient mechanisms that allow users to transfer funds in a secure and fast manner directly from one layer-2 project to another, current layer-2 systems will not be able to scale Ethereum effectively, regardless of their technical solutions. Furthermore, from our results, we conclude that the layer-2 systems that offer similar security guarantees as Ethereum have limited scalability potential, while approaches that offer better performance, sacrifice security and lead to an increase in centralization which runs against the end-goals of permissionless blockchains.},
  author       = {Neiheiser, Ray and Inacio, Gustavo and Rech, Luciana and Montez, Carlos and Matos, Miguel and Rodrigues, Luis},
  issn         = {2169-3536},
  journal      = {IEEE Access},
  keywords     = {General Engineering, General Materials Science, General Computer Science, Electrical and Electronic Engineering},
  pages        = {8651--8662},
  publisher    = {Institute of Electrical and Electronics Engineers},
  title        = {{Practical limitations of Ethereum’s layer-2}},
  doi          = {10.1109/access.2023.3237897},
  volume       = {11},
  year         = {2023},
}

@article{12563,
  abstract     = {he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.},
  author       = {Krokhin, Andrei and Opršal, Jakub and Wrochna, Marcin and Živný, Stanislav},
  issn         = {1095-7111},
  journal      = {SIAM Journal on Computing},
  keywords     = {General Mathematics, General Computer Science},
  number       = {1},
  pages        = {38--79},
  publisher    = {Society for Industrial & Applied Mathematics},
  title        = {{Topology and adjunction in promise constraint satisfaction}},
  doi          = {10.1137/20m1378223},
  volume       = {52},
  year         = {2023},
}

@article{10208,
  abstract     = {It is practical to collect a huge amount of movement data and environmental context information along with the health signals of individuals because there is the emergence of new generations of positioning and tracking technologies and rapid advancements of health sensors. The study of the relations between these datasets and their sequence similarity analysis is of interest to many applications such as health monitoring and recommender systems. However, entering all movement parameters and health signals can lead to the complexity of the problem and an increase in its computational load. In this situation, dimension reduction techniques can be used to avoid consideration of simultaneous dependent parameters in the process of similarity measurement of the trajectories. The present study provides a framework, named CaDRAW, to use spatial–temporal data and movement parameters along with independent context information in the process of measuring the similarity of trajectories. In this regard, the omission of dependent movement characteristic signals is conducted by using an unsupervised feature selection dimension reduction technique. To evaluate the effectiveness of the proposed framework, it was applied to a real contextualized movement and related health signal datasets of individuals. The results indicated the capability of the proposed framework in measuring the similarity and in decreasing the characteristic signals in such a way that the similarity results -before and after reduction of dependent characteristic signals- have small differences. The mean differences between the obtained results before and after reducing the dimension were 0.029 and 0.023 for the round path, respectively.},
  author       = {Goudarzi, Samira and Sharif, Mohammad and Karimipour, Farid},
  issn         = {1868-5145},
  journal      = {Journal of Ambient Intelligence and Humanized Computing},
  keywords     = {general computer science},
  pages        = {2621–2635},
  publisher    = {Springer Nature},
  title        = {{A context-aware dimension reduction framework for trajectory and health signal analyses}},
  doi          = {10.1007/s12652-021-03569-z},
  volume       = {13},
  year         = {2022},
}