Computational Complexity and Local Algorithms
On the Interplay Between Randomness and Computation
Buch in deiner Nähe kaufen
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.
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
Autor*in
Oded Goldreich
Themen in »Computational Complexity and Local Algorithms«
Computational Complexity Local (Sublinear) Algorithms Sublinear Algorithms Property Testing Approximation Algorithms Counting Problems Enumeration Problems Expander Graphs Fine-Grained Complexity Interactive Proof Systems Locally Testable Codes PPT Search Pseudodeterminism Space Complexity