國立高雄大學圖資館 |

Language: English

Back

Property testingproblems and techniques /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Property testingby Arnab Bhattacharyya, Yuichi Yoshida.
Reminder of title:	problems and techniques /
Author:	Bhattacharyya, Arnab.
other author:	Yoshida, Yuichi.
Published:	Singapore :Springer Singapore :2022.
Description:	xix, 427 p. :ill., digital ;24 cm.
Contained By:	Springer Nature eBook
Subject:	Computer algorithms.
Online resource:	https://doi.org/10.1007/978-981-16-8622-1
ISBN:	9789811686221$q(electronic bk.)

Property testingproblems and techniques /
Bhattacharyya, Arnab.

Property testingproblems and techniques /[electronic resource] :by Arnab Bhattacharyya, Yuichi Yoshida. - Singapore :Springer Singapore :2022. - xix, 427 p. :ill., digital ;24 cm.

Chapter 1: Introduction -- Chapter 2: Basic Techniques -- Chapter 3: Strings -- Chapter 4: Graphs in the Adjacency Metrix Model -- Chapter 5: Graphs in the Bounded-Degree Model -- Chapter 6: Functions over Hypercubes -- Chapter 7: Massively Parameterized Model -- Chapter 8: Vectors and Matrices over the Reals -- Chapter 9: Graphs in the Adjacency Matrix Model -- Chapter 10: Graphs in the Bounded-Degree Model -- Chapter 11: Affine-Invariant Properties of Functions -- Chapter 12: Linear Properties of Functions -- Chapter 13: Massively Parameterized Model.

This book introduces important results and techniques in property testing, where the goal is to design algorithms that decide whether their input satisfies a predetermined property in sublinear time, or even in constant time - that is, time is independent of the input size. This book consists of three parts. The first part provides an introduction to the foundations of property testing. The second part studies the testing of specific properties on strings, graphs, functions, and constraint satisfaction problems. Vectors and matrices over real numbers are also covered. The third part is more advanced and explains general conditions, including full characterizations, under which properties are constant-query testable. The first and second parts of the book are intended for first-year graduate students in computer science. They should also be accessible to undergraduate students with the adequate background. The third part can be used by researchers or ambitious graduate students who want to gain a deeper theoretical understanding of property testing.

ISBN: 9789811686221$q(electronic bk.)

Standard No.: 10.1007/978-981-16-8622-1doiSubjects--Topical Terms:

184478
Computer algorithms.

LC Class. No.: QA76.9.A43 / B43 2022

Dewey Class. No.: 005.13

Property testingproblems and techniques /
LDR:02615nmm a2200325 a 4500 001 622351
003 DE-He213
005 20220308093105.0
006 m d
007 cr nn 008maaau
008 221209s2022 si s 0 eng d
020 $a 9789811686221$q(electronic bk.)
020 $a 9789811686214$q(paper)
024 7 $a 10.1007/978-981-16-8622-1 $2 doi
035 $a 978-981-16-8622-1
040 $a GP $c GP
041 0 $a eng
050 4 $a QA76.9.A43 $b B43 2022
072 7 $a UYA $2 bicssc
072 7 $a COM051300 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 005.13 $2 23
090 $a QA76.9.A43 $b B575 2022
100 1 $a Bhattacharyya, Arnab. $3 924157
245 1 0 $a Property testing $h [electronic resource] : $b problems and techniques / $c by Arnab Bhattacharyya, Yuichi Yoshida.
260 $a Singapore : $b Springer Singapore : $b Imprint: Springer, $c 2022.
300 $a xix, 427 p. : $b ill., digital ; $c 24 cm.
505 0 $a Chapter 1: Introduction -- Chapter 2: Basic Techniques -- Chapter 3: Strings -- Chapter 4: Graphs in the Adjacency Metrix Model -- Chapter 5: Graphs in the Bounded-Degree Model -- Chapter 6: Functions over Hypercubes -- Chapter 7: Massively Parameterized Model -- Chapter 8: Vectors and Matrices over the Reals -- Chapter 9: Graphs in the Adjacency Matrix Model -- Chapter 10: Graphs in the Bounded-Degree Model -- Chapter 11: Affine-Invariant Properties of Functions -- Chapter 12: Linear Properties of Functions -- Chapter 13: Massively Parameterized Model.
520 $a This book introduces important results and techniques in property testing, where the goal is to design algorithms that decide whether their input satisfies a predetermined property in sublinear time, or even in constant time - that is, time is independent of the input size. This book consists of three parts. The first part provides an introduction to the foundations of property testing. The second part studies the testing of specific properties on strings, graphs, functions, and constraint satisfaction problems. Vectors and matrices over real numbers are also covered. The third part is more advanced and explains general conditions, including full characterizations, under which properties are constant-query testable. The first and second parts of the book are intended for first-year graduate students in computer science. They should also be accessible to undergraduate students with the adequate background. The third part can be used by researchers or ambitious graduate students who want to gain a deeper theoretical understanding of property testing.
650 0 $a Computer algorithms. $3 184478
650 1 4 $a Design and Analysis of Algorithms. $3 913142
650 2 4 $a Algorithms. $3 184661
700 1 $a Yoshida, Yuichi. $3 924158
710 2 $a SpringerLink (Online service) $3 273601
773 0 $t Springer Nature eBook
856 4 0 $u https://doi.org/10.1007/978-981-16-8622-1
950 $a Computer Science (SpringerNature-11645)