20 Search Results for "Ron-Zewi, Noga"


Document
The Plane Test Is a Local Tester for Multiplicity Codes

Authors: Dan Karliner, Roie Salama, and Amnon Ta-Shma

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order s. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a random line and corrects to the closest uni-variate multiplicity code. However, it was not known whether multiplicity codes are locally testable, and this question has been posed since the introduction of these codes with no progress up to date. In fact, it has been also open whether multiplicity codes can be characterized by local constraints, i.e., if there exists a probabilistic algorithm that queries few symbols of a word c, accepts every c in the code with probability 1, and rejects every c not in the code with nonzero probability. We begin by giving a simple example showing the line test does not give local characterization when d > q. Surprisingly, we then show the plane test is a local characterization when s < q and d < qs-1 for prime q. In addition, we show the s-dimensional test is a local tester for multiplicity codes, when s < q. Combining the two results, we show our main result that the plane test is a local tester for multiplicity codes of degree d < qs-1, with constant rejection probability for constant q, s. Our technique is new. We represent the given input as a possibly very high-degree polynomial, and we show that for some choice of plane, the restriction of the polynomial to the plane is a high-degree bi-variate polynomial. The argument has to work modulo the appropriate kernels, and for that we use Grobner theory, the Combinatorial Nullstellensatz theorem and its generalization to multiplicities. Even given that, the argument is delicate and requires choosing a non-standard monomial order for the argument to work.

Cite as

Dan Karliner, Roie Salama, and Amnon Ta-Shma. The Plane Test Is a Local Tester for Multiplicity Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 14:1-14:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14,
  author =	{Karliner, Dan and Salama, Roie and Ta-Shma, Amnon},
  title =	{{The Plane Test Is a Local Tester for Multiplicity Codes}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{14:1--14:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.14},
  URN =		{urn:nbn:de:0030-drops-165761},
  doi =		{10.4230/LIPIcs.CCC.2022.14},
  annote =	{Keywords: local testing, multiplicity codes, Reed Muller codes}
}
Document
Sublinear-Time Computation in the Presence of Online Erasures

Authors: Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each query to the input object, such an oracle can erase t input values. Our goal is to understand the complexity of basic computational tasks in extremely adversarial situations, where the algorithm’s access to data is blocked during the execution of the algorithm in response to its actions. Specifically, we focus on property testing in the model with online erasures. We show that two fundamental properties of functions, linearity and quadraticity, can be tested for constant t with asymptotically the same complexity as in the standard property testing model. For linearity testing, we prove tight bounds in terms of t, showing that the query complexity is Θ(log t). In contrast to linearity and quadraticity, some other properties, including sortedness and the Lipschitz property of sequences, cannot be tested at all, even for t = 1. Our investigation leads to a deeper understanding of the structure of violations of linearity and other widely studied properties.

Cite as

Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-Time Computation in the Presence of Online Erasures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 90:1-90:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kalemaj_et_al:LIPIcs.ITCS.2022.90,
  author =	{Kalemaj, Iden and Raskhodnikova, Sofya and Varma, Nithin},
  title =	{{Sublinear-Time Computation in the Presence of Online Erasures}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{90:1--90:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.90},
  URN =		{urn:nbn:de:0030-drops-156867},
  doi =		{10.4230/LIPIcs.ITCS.2022.90},
  annote =	{Keywords: Randomized algorithms, property testing, Fourier analysis, linear functions, quadratic functions, Lipschitz and monotone functions, sorted sequences}
}
Document
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four

Authors: Suryajith Chillara

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)


Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to P_d, then C must have size 2^Ω(√dlog{d}). The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC⁰ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC⁰ can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form - sums of powers of polynomials) of 2^(log^O(1) n) size. Thus they argued that a 2^{ω(polylog n)} "functional" lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the "corresponding Boolean function" of Q against non-uniform ACC⁰. In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log²n) ≤ d ≤ n^{0.01}, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O(d/k²) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (∈ VP) over {0,1}^{n²d} must have size n^Ω(k). Since Iterated Matrix Multiplication IMM_{n,d} over {0,1}^{n²d} is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC⁰ from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMM_{n,d} (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMM_{n,d}, for a slightly larger range of individual degree.

Cite as

Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{chillara:LIPIcs.FSTTCS.2021.14,
  author =	{Chillara, Suryajith},
  title =	{{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14},
  URN =		{urn:nbn:de:0030-drops-155251},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.14},
  annote =	{Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication}
}
Document
Variety Evasive Subspace Families

Authors: Zeyu Guo

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
We introduce the problem of constructing explicit variety evasive subspace families. Given a family ℱ of subvarieties of a projective or affine space, a collection ℋ of projective or affine k-subspaces is (ℱ,ε)-evasive if for every 𝒱 ∈ ℱ, all but at most ε-fraction of W ∈ ℋ intersect every irreducible component of 𝒱 with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit k-subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine n-space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of bounded degree in a projective or affine n-space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester-Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a lower bound for the size of k-subspace families that are evasive for degree-d varieties in a projective n-space. When n-k = n^Ω(1), the lower bound is superpolynomial unless d is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties.

Cite as

Zeyu Guo. Variety Evasive Subspace Families. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 20:1-20:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{guo:LIPIcs.CCC.2021.20,
  author =	{Guo, Zeyu},
  title =	{{Variety Evasive Subspace Families}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{20:1--20:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.20},
  URN =		{urn:nbn:de:0030-drops-142949},
  doi =		{10.4230/LIPIcs.CCC.2021.20},
  annote =	{Keywords: algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties}
}
Document
Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)

Authors: Noga Ron-Zewi, Ronen Shaltiel, and Nithin Varma

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
A binary code Enc:{0,1}^k → {0,1}ⁿ is (1/2-ε,L)-list decodable if for every w ∈ {0,1}ⁿ, there exists a set List(w) of size at most L, containing all messages m ∈ {0,1}^k such that the relative Hamming distance between Enc(m) and w is at most 1/2-ε. A q-query local list-decoder for Enc is a randomized procedure Dec that when given oracle access to a string w, makes at most q oracle calls, and for every message m ∈ List(w), with high probability, there exists j ∈ [L] such that for every i ∈ [k], with high probability, Dec^w(i,j) = m_i. We prove lower bounds on q, that apply even if L is huge (say L = 2^{k^{0.9}}) and the rate of Enc is small (meaning that n ≥ 2^{k}): - For ε = 1/k^{ν} for some constant 0 < ν < 1, we prove a lower bound of q = Ω(log(1/δ)/ε²), where δ is the error probability of the local list-decoder. This bound is tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of q = O(log(1/δ)/ε²) for the Hadamard code (which has n = 2^k). This bound extends an earlier work of Grinberg, Shaltiel and Viola (FOCS 2018) which only works if n ≤ 2^{k^ν} and the number of coins tossed by Dec is small (and therefore does not apply to the Hadamard code, or other codes with low rate). - For smaller ε, we prove a lower bound of roughly q = Ω(1/(√ε)). To the best of our knowledge, this is the first lower bound on the number of queries of local list-decoders that gives q ≥ k for small ε. Local list-decoders with small ε form the key component in the celebrated theorem of Goldreich and Levin that extracts a hard-core predicate from a one-way function. We show that black-box proofs cannot improve the Goldreich-Levin theorem and produce a hard-core predicate that is hard to predict with probability 1/2 + 1/𝓁^ω(1) when provided with a one-way function f:{0,1}^𝓁 → {0,1}^𝓁, where f is such that circuits of size poly(𝓁) cannot invert f with probability ρ = 1/2^√𝓁 (or even ρ = 1/2^Ω(𝓁)). This limitation applies to any proof by black-box reduction (even if the reduction is allowed to use nonuniformity and has oracle access to f).

Cite as

Noga Ron-Zewi, Ronen Shaltiel, and Nithin Varma. Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ronzewi_et_al:LIPIcs.ITCS.2021.33,
  author =	{Ron-Zewi, Noga and Shaltiel, Ronen and Varma, Nithin},
  title =	{{Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.33},
  URN =		{urn:nbn:de:0030-drops-135724},
  doi =		{10.4230/LIPIcs.ITCS.2021.33},
  annote =	{Keywords: Local list-decoding, Hard-core predicates, Black-box reduction, Hadamard code}
}
Document
Invited Talk
List-Decodability of Structured Ensembles of Codes (Invited Talk)

Authors: Mary Wootters

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
What combinatorial properties are satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball? What about any cube? In this talk, I will discuss the answer to these questions, along with a more general characterization of the properties that are likely to be satisfied by a random subspace. The motivation for this characterization comes from error correcting codes. I will discuss how to use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes. This talk is based on the works [Mosheiff et al., 2019] and [Guruswami et al., 2020], which are joint works with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.

Cite as

Mary Wootters. List-Decodability of Structured Ensembles of Codes (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 3:1-3:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{wootters:LIPIcs.MFCS.2020.3,
  author =	{Wootters, Mary},
  title =	{{List-Decodability of Structured Ensembles of Codes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{3:1--3:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.3},
  URN =		{urn:nbn:de:0030-drops-126742},
  doi =		{10.4230/LIPIcs.MFCS.2020.3},
  annote =	{Keywords: Error Correcting Codes, List-Decoding}
}
Document
RANDOM
On the List Recoverability of Randomly Punctured Codes

Authors: Ben Lund and Aditya Potukuchi

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.

Cite as

Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lund_et_al:LIPIcs.APPROX/RANDOM.2020.30,
  author =	{Lund, Ben and Potukuchi, Aditya},
  title =	{{On the List Recoverability of Randomly Punctured Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{30:1--30:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.30},
  URN =		{urn:nbn:de:0030-drops-126330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.30},
  annote =	{Keywords: List recovery, randomly punctured codes, Reed-Solomon codes}
}
Document
RANDOM
On List Recovery of High-Rate Tensor Codes

Authors: Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time N^{o(1)}. This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity N^{epsilon} with rate that is exponentially small in 1/epsilon. 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of N^{Omega(1/log log N)} on the product of query complexity and output list size for locally list recovering high-rate tensor codes.

Cite as

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On List Recovery of High-Rate Tensor Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 68:1-68:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.APPROX-RANDOM.2019.68,
  author =	{Kopparty, Swastik and Resch, Nicolas and Ron-Zewi, Noga and Saraf, Shubhangi and Silas, Shashwat},
  title =	{{On List Recovery of High-Rate Tensor Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{68:1--68:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.68},
  URN =		{urn:nbn:de:0030-drops-112832},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.68},
  annote =	{Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes}
}
Document
Resolution and the Binary Encoding of Combinatorial Principles

Authors: Stefan Dantchev, Nicola Galesi, and Barnaby Martin

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
Res(s) is an extension of Resolution working on s-DNFs. We prove tight n^{Omega(k)} lower bounds for the size of refutations of the binary version of the k-Clique Principle in Res(o(log log n)). Our result improves that of Lauria, Pudlák et al. [Massimo Lauria et al., 2017] who proved the lower bound for Res(1), i.e. Resolution. The exact complexity of the (unary) k-Clique Principle in Resolution is unknown. To prove the lower bound we do not use any form of the Switching Lemma [Nathan Segerlind et al., 2004], instead we apply a recursive argument specific for binary encodings. Since for the k-Clique and other principles lower bounds in Resolution for the unary version follow from lower bounds in Res(log n) for their binary version we start a systematic study of the complexity of proofs in Resolution-based systems for families of contradictions given in the binary encoding. We go on to consider the binary version of the weak Pigeonhole Principle Bin-PHP^m_n for m>n. Using the the same recursive approach we prove the new result that for any delta>0, Bin-PHP^m_n requires proofs of size 2^{n^{1-delta}} in Res(s) for s=o(log^{1/2}n). Our lower bound is almost optimal since for m >= 2^{sqrt{n log n}} there are quasipolynomial size proofs of Bin-PHP^m_n in Res(log n). Finally we propose a general theory in which to compare the complexity of refuting the binary and unary versions of large classes of combinatorial principles, namely those expressible as first order formulae in Pi_2-form and with no finite model.

Cite as

Stefan Dantchev, Nicola Galesi, and Barnaby Martin. Resolution and the Binary Encoding of Combinatorial Principles. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dantchev_et_al:LIPIcs.CCC.2019.6,
  author =	{Dantchev, Stefan and Galesi, Nicola and Martin, Barnaby},
  title =	{{Resolution and the Binary Encoding of Combinatorial Principles}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.6},
  URN =		{urn:nbn:de:0030-drops-108287},
  doi =		{10.4230/LIPIcs.CCC.2019.6},
  annote =	{Keywords: Proof complexity, k-DNF resolution, binary encodings, Clique and Pigeonhole principle}
}
Document
Almost Optimal Distribution-Free Junta Testing

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
We consider the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}^n. Chen, Liu, Servedio, Sheng and Xie [Zhengyang Liu et al., 2018] showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes O~(k^2)/epsilon queries. In this paper, we give a simple two-sided error adaptive algorithm that makes O~(k/epsilon) queries.

Cite as

Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.CCC.2019.2,
  author =	{Bshouty, Nader H.},
  title =	{{Almost Optimal Distribution-Free Junta Testing}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2},
  URN =		{urn:nbn:de:0030-drops-108249},
  doi =		{10.4230/LIPIcs.CCC.2019.2},
  annote =	{Keywords: Distribution-free property testing, k-Junta}
}
Document
From Local to Robust Testing via Agreement Testing

Authors: Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is robust if for non-codewords it satisfies the stronger property that the average distance of local views from accepting views is proportional to the distance from the code. Robust testing is an important component in constructions of locally testable codes and probabilistically checkable proofs as it allows for composition of local tests. In this work we show that for certain codes, any (natural) local tester can be converted to a roubst tester with roughly the same number of queries. Our result holds for the class of affine-invariant lifted codes which is a broad class of codes that includes Reed-Muller codes, as well as recent constructions of high-rate locally testable codes (Guo, Kopparty, and Sudan, ITCS 2013). Instantiating this with known local testing results for lifted codes gives a more direct proof that improves some of the parameters of the main result of Guo, Haramaty, and Sudan (FOCS 2015), showing robustness of lifted codes. To obtain the above transformation we relate the notions of local testing and robust testing to the notion of agreement testing that attempts to find out whether valid partial assignments can be stitched together to a global codeword. We first show that agreement testing implies robust testing, and then show that local testing implies agreement testing. Our proof is combinatorial, and is based on expansion / sampling properties of the collection of local views of local testers. Thus, it immediately applies to local testers of lifted codes that query random affine subspaces in F_q^m, and moreover seems amenable to extension to other families of locally testable codes with expanding families of local views.

Cite as

Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi. From Local to Robust Testing via Agreement Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dinur_et_al:LIPIcs.ITCS.2019.29,
  author =	{Dinur, Irit and Harsha, Prahladh and Kaufman, Tali and Ron-Zewi, Noga},
  title =	{{From Local to Robust Testing via Agreement Testing}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.29},
  URN =		{urn:nbn:de:0030-drops-101221},
  doi =		{10.4230/LIPIcs.ITCS.2019.29},
  annote =	{Keywords: Local testing, Robust testing, Agreement testing, Affine-invariant codes, Lifted codes}
}
Document
Erasures vs. Errors in Local Decoding and Property Testing

Authors: Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures. Motivated by applications in property testing, we begin our investigation with local list decoding in the presence of erasures. We prove an analog of a famous result of Goldreich and Levin on local list decodability of the Hadamard code. Specifically, we show that the Hadamard code is locally list decodable in the presence of a constant fraction of erasures, arbitrary close to 1, with list sizes and query complexity better than in the Goldreich-Levin theorem. We use this result to exhibit a property which is testable with a number of queries independent of the length of the input in the presence of erasures, but requires a number of queries that depends on the input length, n, for tolerant testing. We further study approximate locally list decodable codes that work against erasures and use them to strengthen our separation by constructing a property which is testable with a constant number of queries in the presence of erasures, but requires n^{Omega(1)} queries for tolerant testing. Next, we study the general relationship between local decoding in the presence of errors and in the presence of erasures. We observe that every locally (uniquely or list) decodable code that works in the presence of errors also works in the presence of twice as many erasures (with the same parameters up to constant factors). We show that there is also an implication in the other direction for locally decodable codes (with unique decoding): specifically, that the existence of a locally decodable code that works in the presence of erasures implies the existence of a locally decodable code that works in the presence of errors and has related parameters. However, it remains open whether there is an implication in the other direction for locally list decodable codes. We relate this question to other open questions in local decoding.

Cite as

Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures vs. Errors in Local Decoding and Property Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 63:1-63:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{raskhodnikova_et_al:LIPIcs.ITCS.2019.63,
  author =	{Raskhodnikova, Sofya and Ron-Zewi, Noga and Varma, Nithin},
  title =	{{Erasures vs. Errors in Local Decoding and Property Testing}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{63:1--63:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.63},
  URN =		{urn:nbn:de:0030-drops-101568},
  doi =		{10.4230/LIPIcs.ITCS.2019.63},
  annote =	{Keywords: Error-correcting codes, probabilistically checkable proofs (PCPs) of proximity, Hadamard code, local list decoding, tolerant testing}
}
Document
Correlation in Hard Distributions in Communication Complexity

Authors: Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously studied extreme cases: the (standard) randomised communication complexity and the case of distributional complexity under product distributions. - We give a tight characterisation of the randomised complexity of Disjointness under distributions with mutual information k, showing that it is Theta(sqrt(n(k+1))) for all 0 <= k <= n. This smoothly interpolates between the lower bounds of Babai, Frankl and Simon for the product distribution case (k=0), and the bound of Razborov for the randomised case. The upper bounds improve and generalise what was known for product distributions, and imply that any tight bound for Disjointness needs Omega(n) bits of mutual information in the corresponding distribution. - We study the same question in the distributional quantum setting, and show a lower bound of Omega((n(k+1))^{1/4}), and an upper bound (via constructing communication protocols), matching up to a logarithmic factor. - We show that there are total Boolean functions f_d that have distributional communication complexity O(log(n)) under all distributions of information up to o(n), while the (interactive) distributional complexity maximised over all distributions is Theta(log(d)) for n <= d <= 2^{n/100}. This shows, in particular, that the correlation needed to show that a problem is hard can be much larger than the communication complexity of the problem. - We show that in the setting of one-way communication under product distributions, the dependence of communication cost on the allowed error epsilon is multiplicative in log(1/epsilon) - the previous upper bounds had the dependence of more than 1/epsilon. This result, for the first time, explains how one-way communication complexity under product distributions is stronger than PAC-learning: both tasks are characterised by the VC-dimension, but have very different error dependence (learning from examples, it costs more to reduce the error).

Cite as

Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck. Correlation in Hard Distributions in Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 544-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bottesch_et_al:LIPIcs.APPROX-RANDOM.2015.544,
  author =	{Bottesch, Ralph Christian and Gavinsky, Dmitry and Klauck, Hartmut},
  title =	{{Correlation in Hard Distributions in Communication Complexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{544--572},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.544},
  URN =		{urn:nbn:de:0030-drops-53234},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.544},
  annote =	{Keywords: communication complexity; information theory}
}
Document
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

Authors: Mark Bun and Thomas Steinke

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
Low-degree polynomial approximations to the sign function underlie pseudorandom generators for halfspaces, as well as algorithms for agnostically learning halfspaces. We study the limits of these constructions by proving inapproximability results for the sign function. First, we investigate the derandomization of Chernoff-type concentration inequalities. Schmidt et al. (SIAM J. Discrete Math. 1995) showed that a tail bound of delta can be established for sums of Bernoulli random variables with only O(log(1/delta))-wise independence. We show that their results are tight up to constant factors. Secondly, the “polynomial regression” algorithm of Kalai et al. (SIAM J. Comput. 2008) shows that halfspaces can be efficiently learned with respect to log-concave distributions on R^n in the challenging agnostic learning model. The power of this algorithm relies on the fact that under log-concave distributions, halfspaces can be approximated arbitrarily well by low-degree polynomials. In contrast, we exhibit a large class of non-log-concave distributions under which polynomials of any degree cannot approximate the sign function to within arbitrarily low error.

Cite as

Mark Bun and Thomas Steinke. Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 625-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2015.625,
  author =	{Bun, Mark and Steinke, Thomas},
  title =	{{Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{625--644},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.625},
  URN =		{urn:nbn:de:0030-drops-53274},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.625},
  annote =	{Keywords: Polynomial Approximations, Pseudorandomness, Concentration, Learning Theory, Halfspaces}
}
Document
The Hardness of Approximation of Euclidean k-Means

Authors: Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)


Abstract
The Euclidean k-means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of n points in Euclidean space R^d, and the goal is to choose k center points in R^d so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general k and a (1+c)-approximation which runs in time poly(n) exp(k/c). At the other extreme, the only known computational complexity result for this problem is NP-hardness [Aloise et al.'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in R^d can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all k, d. In this paper we provide the first hardness of approximation for the Euclidean k-means problem. Concretely, we show that there exists a constant c > 0 such that it is NP-hard to approximate the k-means objective to within a factor of (1+c). We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform G, a known hard vertex cover instance, by taking a graph product with a suitably chosen graph H, and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.

Cite as

Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 754-767, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{awasthi_et_al:LIPIcs.SOCG.2015.754,
  author =	{Awasthi, Pranjal and Charikar, Moses and Krishnaswamy, Ravishankar and Sinop, Ali Kemal},
  title =	{{The Hardness of Approximation of Euclidean k-Means}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{754--767},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.754},
  URN =		{urn:nbn:de:0030-drops-51178},
  doi =		{10.4230/LIPIcs.SOCG.2015.754},
  annote =	{Keywords: Euclidean k-means, Hardness of Approximation, Vertex Cover}
}
  • Refine by Author
  • 4 Ron-Zewi, Noga
  • 3 Varma, Nithin
  • 2 Raskhodnikova, Sofya
  • 1 Awasthi, Pranjal
  • 1 Bottesch, Ralph Christian
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Error-correcting codes
  • 2 Mathematics of computing → Coding theory
  • 2 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Pseudorandomness and derandomization
  • Show More...

  • Refine by Keyword
  • 2 Hadamard code
  • 2 Property testing
  • 2 property testing
  • 1 Affine-invariant codes
  • 1 Agreement testing
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 7 2015
  • 5 2019
  • 3 2021
  • 2 2020
  • 2 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail