[图书][B] Introduction to property testing
O Goldreich - 2017 - books.google.com
Property testing is concerned with the design of super-fast algorithms for the structural
analysis of large quantities of data. The aim is to unveil global features of the data, such as …
analysis of large quantities of data. The aim is to unveil global features of the data, such as …
[PDF][PDF] Characterizing Direct Product Testing via Coboundary Expansion
M Bafna, D Minzer - Proceedings of the 56th Annual ACM Symposium on …, 2024 - dl.acm.org
A d-dimensional simplicial complex X is said to support a direct product tester if any locally
consistent function defined on its k-faces (where k≪ d) necessarily come from a function …
consistent function defined on its k-faces (where k≪ d) necessarily come from a function …
On approximability of satisfiable k-CSPs: I
A Bhangale, S Khot, D Minzer - Proceedings of the 54th Annual ACM …, 2022 - dl.acm.org
We consider the P-CSP problem for 3-ary predicates P on satisfiable instances. We show
that under certain conditions on P and a (1, s) integrality gap instance of the P-CSP problem …
that under certain conditions on P and a (1, s) integrality gap instance of the P-CSP problem …
High dimensional expanders imply agreement expanders
I Dinur, T Kaufman - 2017 IEEE 58th Annual Symposium on …, 2017 - ieeexplore.ieee.org
We show that high dimensional expanders imply derandomized direct product tests, with a
number of subsets that is linear in the size of the universe. Direct product tests belong to a …
number of subsets that is linear in the size of the universe. Direct product tests belong to a …
Near-linear time decoding of ta-shma's codes via splittable regularity
FG Jeronimo, S Srivastava, M Tulsiani - … of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes
of distance 1/2− є/2 and rate Ω (є2). In a breakthrough result, Ta-Shma [STOC 2017] …
of distance 1/2− є/2 and rate Ω (є2). In a breakthrough result, Ta-Shma [STOC 2017] …
[图书][B] Property Testing: Problems and Techniques
A Bhattacharyya, Y Yoshida - 2022 - books.google.com
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 …
to design algorithms that decide whether their input satisfies a predetermined property in …
List decoding of direct sum codes
VL Alev, FG Jeronimo, D Quintana, S Srivastava… - Proceedings of the …, 2020 - SIAM
We consider families of codes obtained by “lifting” a base code through operations such as k-
XOR applied to “local views” of codewords of, according to a suitable k-uniform hypergraph …
XOR applied to “local views” of codewords of, according to a suitable k-uniform hypergraph …
Friedgut--Kalai--Naor theorem for slices of the Boolean cube
Y Filmus - arXiv preprint arXiv:1410.7834, 2014 - arxiv.org
The Friedgut--Kalai--Naor theorem states that if a Boolean function $ f\colon\{0, 1\}^ n\to\{0,
1\} $ is close (in $ L^ 2$-distance) to an affine function $\ell (x_1,..., x_n)= c_0+\sum_i c_i x_i …
1\} $ is close (in $ L^ 2$-distance) to an affine function $\ell (x_1,..., x_n)= c_0+\sum_i c_i x_i …
Unique Decoding of Explicit -balanced Codes Near the Gilbert-Varshamov Bound
FG Jeronimo, D Quintana, S Srivastava… - 2020 IEEE 61st …, 2020 - ieeexplore.ieee.org
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes
of distance 1/2-ε and rate Ω(ε^2) (where an upper bound of O(ε^2\log(1/ε)) is known). Ta …
of distance 1/2-ε and rate Ω(ε^2) (where an upper bound of O(ε^2\log(1/ε)) is known). Ta …
List agreement expansion from coboundary expansion
R Gotlib, T Kaufman - arXiv preprint arXiv:2210.15714, 2022 - arxiv.org
One of the key components in PCP constructions are agreement tests. In agreement test the
tester is given access to subsets of fixed size of some set, each equipped with an …
tester is given access to subsets of fixed size of some set, each equipped with an …