LEADER 04191nam 22005655 450 001 996664548203316 005 20250610130239.0 010 $a3-031-88946-0 024 7 $a10.1007/978-3-031-88946-2 035 $a(CKB)39239631900041 035 $a(MiAaPQ)EBC32151024 035 $a(Au-PeEL)EBL32151024 035 $a(DE-He213)978-3-031-88946-2 035 $a(EXLCZ)9939239631900041 100 $a20250610d2025 u| 0 101 0 $aeng 135 $aur||||||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aComputational Complexity and Local Algorithms $eOn the Interplay Between Randomness and Computation /$fedited by Oded Goldreich 205 $a1st ed. 2025. 210 1$aCham :$cSpringer Nature Switzerland :$cImprint: Springer,$d2025. 215 $a1 online resource (1007 pages) 225 1 $aLecture Notes in Computer Science,$x1611-3349 ;$v15700 311 08$a3-031-88945-2 327 $a-. 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. 330 $aThis 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. 410 0$aLecture Notes in Computer Science,$x1611-3349 ;$v15700 606 $aAlgorithms 606 $aComputational complexity 606 $aMathematics$xData processing 606 $aDesign and Analysis of Algorithms 606 $aComputational Complexity 606 $aComputational Mathematics and Numerical Analysis 615 0$aAlgorithms. 615 0$aComputational complexity. 615 0$aMathematics$xData processing. 615 14$aDesign and Analysis of Algorithms. 615 24$aComputational Complexity. 615 24$aComputational Mathematics and Numerical Analysis. 676 $a005.13 700 $aGoldreich$b Oded$066329 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996664548203316 996 $aComputational Complexity and Local Algorithms$94393590 997 $aUNISA