KI-Beratung Beta

Produktbild: Computational Complexity and Local Algorithms
Band 15700 - 17%

Computational Complexity and Local Algorithms On the Interplay Between Randomness and Computation

17% sparen

72,99 € UVP 87,99 €

inkl. gesetzl. MwSt., Versandkostenfrei


Beschreibung

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...

Beschreibung

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.

Portrait


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 (1983–1986), a faculty member at the Technion (1986–1994), a visiting scientist at MIT (1995–1998), and a Radcliffe fellow at Harvard (2003–2004). 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 (1995–1997), a science scholar at the Bunting Institute, Radcliffe (1997–1998), and a Radcliffe fellow at Harvard (2003–2004). 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.


 

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

10.06.2025

Abbildungen

X, 451 p. 11 illus., 9 illus. in color.

Herausgeber Oded Goldreich

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

10.06.2025

Abbildungen

X, 451 p. 11 illus., 9 illus. in color.

Herausgeber Oded Goldreich
Verlag Springer
Seitenzahl

451

Maße (L/B/H)

23,5/15,5/2,5 cm

Gewicht

698 g

Sprache

Englisch

ISBN

978-3-031-88945-5

Herstelleradresse

Springer-Verlag KG
Sachsenplatz 4-6
1201 Wien
AT

Email: ProductSafety@springernature.com

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)

  • Produktbild: Computational Complexity and Local Algorithms

  • -. 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.