Computational Complexity and Local Algorithms
Springer International Publishing (Verlag)
978-3-031-88945-5 (ISBN)
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.
Oded Goldreich (oded.goldreich@weizmann.ac.il) is a Meyer W. WeisgalProfessor at the Faculty of Mathematics and Computer Science of the WeizmannInstitute of Science, Israel. Oded was born in 1957, and completed his graduatestudies in 1983 under the supervision of Shimon Even. He was a post-doctoralfellow at MIT (1983-86), a faculty member at the Technion (1986-94), a vis-iting scientist at MIT (1995-98), and a Radcliffe fellow at Harvard (2003/04).Since 1995, he is a member of the Computer Science and Applied MathematicsDepartment of the Weizmann Institute. He is the author of "Modern Cryptog-raphy, Probabilistic Proofs and Pseudorandomness" (Springer, 1998), the two-volume work "Foundations of Cryptography" (Cambridge University Press, 2001and 2004), "Computational Complexity: A Conceptual Perspective" (CambridgeUniversity Press, 2008), and "Introduction to Property Testing" (CambridgeUniversity Press, 2017).
Nader H. Bshouty (bshouty@cs.technion.ac.il) is a Professor of ComputerScience at the Technion - Israel Institute of Technology, Haifa, Israel. Born in1960, he completed his doctoral studies in Computer Science in 1989 at theTechnion under the supervision of Michael Kaminski. From 1989 to 1998, heheld academic positions at the University of Calgary, Canada. Since 1999, hehas been a Professor at the Technion. His research focuses on ComputationalLearning Theory, Property Testing, Models of Computation, and the Complexityof Algebraic Computations.
Dana Ron (danar@eng.tau.ac.il) is the Lazarus Brothers Chair of ComputerEngineering at the School of Electrical Engineering of Tel Aviv University, Israel.Dana was born in 1964, and completed her graduate studies in 1995 under thesupervision of Naftali Tishby. She was an NSF post-doctoral fellow at MIT(1995-97), a science scholar at the Bunting Institute, Radcliffe (1997-98), and aRadcliffe fellow at Harvard (2003/04). Since 1998 she is a faculty member in TelAviv University. She is a fellow of the EATCS and ACM.
Laliv Tauber (lalivta@gmail.com) completed her master thesis at the Weiz-mann Institute of Science in 2024.
-. 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.
| Erscheinungsdatum | 10.06.2025 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | X, 451 p. 11 illus., 9 illus. in color. |
| Verlagsort | Cham |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Themenwelt | Mathematik / Informatik ► Informatik ► Theorie / Studium |
| Mathematik / Informatik ► Mathematik ► Analysis | |
| Schlagworte | approximation algorithms • Complexity theory • Computation • Computational Complexity • counting problems • enumeration problems • Expander Graphs • explicit construction of expander graphs • fine grained complexity • Fine-Grained Complexity • Interactive Proof Systems • Local algorithms • Locally decodable codes • locally testable codes • Local (Sublinear) Algorithms • PPT Search • PPT-search problems • property testing • pseudodeterminism • space complexity • Sublinear algorithms • testing graph properties in the bounded-degree graph model • theoretical computer science |
| ISBN-10 | 3-031-88945-2 / 3031889452 |
| ISBN-13 | 978-3-031-88945-5 / 9783031889455 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
