- ホーム
- > 洋書
- > ドイツ書
- > Mathematics, Sciences & Technology
- > Computer & Internet
- > general surveys & lexicons
Full Description
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.
Contents
-. 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.
