Computational Complexity and Local Algorithms

This volume contains a collection of studies in the areas of complexity theory and local algorithms. A common theme in most of the papers is the interplay between randomness and computation. This interplay is pivotal to some parts of complexity theory and is essential for local algorithms.

The works included address a variety of topics in the areas of complexity theory and local algorithms. Within complexity theory the topics include approximation algorithms, counting problems, enumeration problems, explicit construction of expander graphs, fine grained complexity, interactive proof systems, PPT-search and pseudodeterminism, space complexity, and worst-case to average-case reductions. Within local algorithms the focus is mostly on property testing and on locally testable and decodable codes. In particular, many of the works seek to advance the study of testing graph properties in the bounded-degree graph model. Other topics in property testing include testing group properties and testing properties of affine subspaces.

State-of-the-art research in Computational Complexity and Local Algorithms Contributions by well-known experts in the field Represents a unique approach to deep theoretical computer science problems

Autorentext

Oded Goldreich is a Meyer W. Weisgal Professor at the Weizmann Institute of Science, Israel. Oded completed his graduate studies in 1983 under the supervision of Shimon Even, he was a postdoctoral fellow at MIT (19831986), a faculty member at the Technion (19861994), a visiting scientist at MIT (19951998), and a Radcliffe fellow at Harvard (20032004). Since 1995 he has been a member of the Computer Science and Applied Mathematics department at the Weizmann Institute. He is the author of Modern Cryptography, Probabilistic Proofs and Pseudorandomness (Springer, 1998), the two-volume work Foundations of Cryptography (Cambridge University Press, 2001, 2004), Computational Complexity: A Conceptual Perspective (Cambridge University Press, 2008), and Introduction to Property Testing (Cambridge University Press, 2017).

Nader H. Bshouty is a Professor of Computer Science at the Technion Israel Institute of Technology, Israel. He completed his doctoral studies in Computer Science in 1989 at the Technion under the supervision of Michael Kaminski, from 1989 to 1998, he held academic positions at the University of Calgary, Canada. Since 1999, he has been a professor at the Technion. His research focuses on Computational Learning Theory, Property Testing, Models of Computation, and the Complexity of Algebraic Computations.

Dana Ron is the Lazarus Brothers Chair of Computer Engineering in the School of Electrical Engineering at Tel Aviv University, Israel. Dana completed her graduate studies in 1995 under the supervision of Naftali Tishby, she was an NSF postdoctoral fellow at MIT (19951997), a science scholar at the Bunting Institute, Radcliffe (19971998), and a Radcliffe fellow at Harvard (20032004). Since 1998 she has been a faculty member at Tel Aviv University. She is a fellow of the EATCS and ACM.

Laliv Tauber completed her master's thesis at the Weizmann Institute of Science in 2024.

Inhalt

-. On defining PPT-search problems.- -. Multi-pseudodeterministic algorithms.- On counting t-cliques Mod 2.- On coarse and fine approximate counting of t-cliques.- On the complexity of enumerating ordered sets.- On the Cook-Mertz Tree Evaluation procedure.- Solving Tree Evaluation in o(log n · log log n) space.- On parallel repetitions of interactive proof systems.- On locally-characterized expander graphs (a survey).- On the Locally Testable Code of Dinur et al. (2021).- On the lower bound on the length of relaxed Locally Decodable Codes.- On the relaxed LDC of BGHSV: A survey that corrects the record.- On the complexity of estimating the Effective Support Size.- Robust Self-Ordering versus Local Self-Ordering.- On Testing Hamiltonicity in the Bounded Degree Graph Model.- Testing Isomorphism in the Bounded-Degree Graph Model.- On Testing Isomorphism to a fixed graph in the Bounded-Degree Graph Model.- On Testing Asymmetry in the Bounded Degree Graph Model.- On the query complexity of testing local graph properties in the Bounded-Degree Graph Model.- Testing in the bounded-degree graph model with degree bound two.- On properties that are non-trivial to test.- One-Sided Error Testing of Monomials and Affine Subspaces.- On testing group properties.