國立高雄大學圖資館 |

登入

回首頁

Computational complexity and local algorithmson the interplay between randomness and computation /

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Computational complexity and local algorithmsedited by Oded Goldreich.
其他題名:	on the interplay between randomness and computation /
其他作者:	Goldreich, Oded.
出版者:	Cham :Springer Nature Switzerland :2025.
面頁冊數:	x, 451 p. :ill. (chiefly color), digital ;24 cm.
Contained By:	Springer Nature eBook
標題:	Computational complexity.
電子資源:	https://doi.org/10.1007/978-3-031-88946-2
ISBN:	9783031889462$q(electronic bk.)

Computational complexity and local algorithmson the interplay between randomness and computation /
Computational complexity and local algorithmson the interplay between randomness and computation /[electronic resource] :edited by Oded Goldreich. - Cham :Springer Nature Switzerland :2025. - x, 451 p. :ill. (chiefly color), digital ;24 cm. - Lecture notes in computer science,157001611-3349 ;. - Lecture notes in computer science ;4891..

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.

ISBN: 9783031889462$q(electronic bk.)

Standard No.: 10.1007/978-3-031-88946-2doiSubjects--Topical Terms:

185313
Computational complexity.

LC Class. No.: QA267.7

Dewey Class. No.: 511.3

Computational complexity and local algorithmson the interplay between randomness and computation /
LDR:02165nmm a2200337 a 4500 001 683051
003 DE-He213
005 20250610130239.0
006 m d
007 cr nn 008maaau
008 251212s2025 sz s 0 eng d
020 $a 9783031889462$q(electronic bk.)
020 $a 9783031889455$q(paper)
024 7 $a 10.1007/978-3-031-88946-2 $2 doi
035 $a 978-3-031-88946-2
040 $a GP $c GP
041 0 $a eng
050 4 $a QA267.7
072 7 $a UYA $2 bicssc
072 7 $a COM014000 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 511.3 $2 23
090 $a QA267.7 $b .C738 2025
245 0 0 $a Computational complexity and local algorithms $h [electronic resource] : $b on the interplay between randomness and computation / $c edited by Oded Goldreich.
260 $a Cham : $b Springer Nature Switzerland : $b Imprint: Springer, $c 2025.
300 $a x, 451 p. : $b ill. (chiefly color), digital ; $c 24 cm.
338 $a online resource $b cr $2 rdacarrier
490 1 $a Lecture notes in computer science, $x 1611-3349 ; $v 15700
520 $a 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.
650 0 $a Computational complexity. $3 185313
650 0 $a Algorithms. $3 184661
650 1 4 $a Design and Analysis of Algorithms. $3 913142
650 2 4 $a Computational Complexity. $3 913441
650 2 4 $a Computational Mathematics and Numerical Analysis. $3 274020
700 1 $a Goldreich, Oded. $3 279127
710 2 $a SpringerLink (Online service) $3 273601
773 0 $t Springer Nature eBook
830 0 $a Lecture notes in computer science ; $v 4891. $3 383229
856 4 0 $u https://doi.org/10.1007/978-3-031-88946-2
950 $a Computer Science (SpringerNature-11645)