國立虎尾科技大學 |

Computational complexity and local algorithms = on the interplay between randomness and computation /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Computational complexity and local algorithms/ edited by Oded Goldreich.
Reminder of title:	on the interplay between randomness and computation /
other author:	Goldreich, Oded.
Published:	Cham :Springer Nature Switzerland : : 2025.,
Description:	x, 451 p. :ill. (chiefly color), digital ; : 24 cm.;
Contained By:	Springer Nature eBook
Subject:	Computational complexity. -
Online resource:	https://doi.org/10.1007/978-3-031-88946-2
ISBN:	9783031889462

Computational complexity and local algorithms = on 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 ;6140..

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

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

527777
Computational complexity.

LC Class. No.: QA267.7

Dewey Class. No.: 511.3

Computational complexity and local algorithms = on the interplay between randomness and computation /
LDR:02164nam a2200337 a 4500 001 1159389
003 DE-He213
005 20250610130239.0
006 m d
007 cr nn 008maaau
008 251029s2025 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 : $c 2025. $b Springer Nature Switzerland : $b Imprint: Springer,
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 527777
650 0 $a Algorithms. $3 527865
650 1 4 $a Design and Analysis of Algorithms. $3 1365721
650 2 4 $a Computational Complexity. $3 1366362
650 2 4 $a Computational Mathematics and Numerical Analysis. $3 669338
700 1 $a Goldreich, Oded. $3 786282
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
830 0 $a Lecture notes in computer science ; $v 6140. $3 744199
856 4 0 $u https://doi.org/10.1007/978-3-031-88946-2
950 $a Computer Science (SpringerNature-11645)