14 Search Results for "Dvir, Zeev"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.69
Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors

Authors: Kuan Cheng and Ruiyang Wu

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

Abstract
We study randomness extractors in AC⁰ and NC¹. For the AC⁰ setting, we give a logspace-uniform construction such that for every k ≥ n/poly log n, ε ≥ 2^{-poly log n}, it can extract from an arbitrary (n, k) source, with a small constant fraction entropy loss, and the seed length is O(log n/(ε)). The seed length and output length are optimal up to constant factors matching the parameters of the best polynomial time construction such as [Guruswami et al., 2009]. The range of k and ε almost meets the lower bound in [Goldreich et al., 2015] and [Cheng and Li, 2018]. We also generalize the main lower bound of [Goldreich et al., 2015] for extractors in AC⁰, showing that when k < n/poly log n, even strong dispersers do not exist in non-uniform AC⁰. For the NC¹ setting, we also give a logspace-uniform extractor construction with seed length O(log n/(ε)) and a small constant fraction entropy loss in the output. It works for every k ≥ O(log² n), ε ≥ 2^{-O(√k)}. Our main techniques include a new error reduction process and a new output stretch process, based on low-depth circuit implementations for mergers, condensers, and somewhere extractors.
Cite as

Kuan Cheng and Ruiyang Wu. Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.69,
  author =	{Cheng, Kuan and Wu, Ruiyang},
  title =	{{Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{69:1--69:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.69},
  URN =		{urn:nbn:de:0030-drops-210623},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.69},
  annote =	{Keywords: randomness extractor, uniform AC⁰, error reduction, uniform NC¹, disperser}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.6
Information-Theoretic Single-Server PIR in the Shuffle Model

Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every γ > 0, the protocol has O(n^{γ}) communication and computation costs per (stateless) client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.
Cite as

Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma. Information-Theoretic Single-Server PIR in the Shuffle Model. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.ITC.2024.6,
  author =	{Ishai, Yuval and Kelkar, Mahimna and Lee, Daniel and Ma, Yiping},
  title =	{{Information-Theoretic Single-Server PIR in the Shuffle Model}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.6},
  URN =		{urn:nbn:de:0030-drops-205142},
  doi =		{10.4230/LIPIcs.ITC.2024.6},
  annote =	{Keywords: Private information retrieval, Shuffle model}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.8
Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed n-bit RLCCs with O(log^{69} n) queries. Their construction relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs. As for lower bounds, Gur and Lachish (SICOMP 2021) proved that any asymptotically-good RLCC must make Ω̃(√{log n}) queries. Hence emerges the intriguing question regarding the identity of the least value 1/2 ≤ e ≤ 69 for which asymptotically-good RLCCs with query complexity (log n)^{e+o(1)} exist. In this work, we make substantial progress in narrowing the gap by devising asymptotically-good RLCCs with a query complexity of (log n)^{2+o(1)}. The key insight driving our work lies in recognizing that the strong guarantee of local testability overshoots the requirements for the Kumar-Mon reduction. In particular, we prove that we can replace the LTCs by "vanilla" expander codes which indeed have the necessary property: local testability in the code’s vicinity.
Cite as

Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.8},
  URN =		{urn:nbn:de:0030-drops-204045},
  doi =		{10.4230/LIPIcs.CCC.2024.8},
  annote =	{Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.18
Pseudorandomness, Symmetry, Smoothing: I

Authors: Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that - achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. - have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. - rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.
Cite as

Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, Symmetry, Smoothing: I. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 18:1-18:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{derksen_et_al:LIPIcs.CCC.2024.18,
  author =	{Derksen, Harm and Ivanov, Peter and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Pseudorandomness, Symmetry, Smoothing: I}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{18:1--18:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.18},
  URN =		{urn:nbn:de:0030-drops-204144},
  doi =		{10.4230/LIPIcs.CCC.2024.18},
  annote =	{Keywords: pseudorandomness, k-wise uniform distributions, small-bias distributions, noise, symmetric tests, thresholds, Krawtchouk polynomials}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.20
Lower Bounds for Set-Multilinear Branching Programs

Authors: Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
In this paper, we prove super-polynomial lower bounds for the model of sum of ordered set-multilinear algebraic branching programs, each with a possibly different ordering (∑smABP). Specifically, we give an explicit nd-variate polynomial of degree d such that any ∑smABP computing it must have size n^ω(1) for d as low as ω(log n). Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for d = poly(n), we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP. The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (TAMC, 2024), which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs - for a polynomial of sufficiently low degree - would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant’s longstanding conjecture that the permanent polynomial can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by O(log n/ log log n), then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind & Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi & Saxena (TAMC, 2024), as well as the works of Ramya & Rao (Theor. Comput. Sci., 2020) and Ghoshal & Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general ∑smABP.
Cite as

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. Lower Bounds for Set-Multilinear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2024.20,
  author =	{Chatterjee, Prerona and Kush, Deepanshu and Saraf, Shubhangi and Shpilka, Amir},
  title =	{{Lower Bounds for Set-Multilinear Branching Programs}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.20},
  URN =		{urn:nbn:de:0030-drops-204167},
  doi =		{10.4230/LIPIcs.CCC.2024.20},
  annote =	{Keywords: Lower Bounds, Algebraic Branching Programs, Set-multilinear polynomials}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.108
Two-Source and Affine Non-Malleable Extractors for Small Entropy

Authors: Xin Li and Yan Zhong

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Non-malleable extractors are generalizations and strengthening of standard randomness extractors, that are resilient to adversarial tampering. Such extractors have wide applications in cryptography and have become important cornerstones in recent breakthroughs of explicit constructions of two-source extractors and affine extractors for small entropy. However, explicit constructions of non-malleable extractors appear to be much harder than standard extractors. Indeed, in the well-studied models of two-source and affine non-malleable extractors, the previous best constructions only work for entropy rate > 2/3 and 1-γ for some small constant γ > 0 respectively by Li (FOCS' 23). In this paper, we present explicit constructions of two-source and affine non-malleable extractors that match the state-of-the-art constructions of standard ones for small entropy. Our main results include: - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k ≥ log^C n and polynomially small error, matching the parameters of standard extractors by Chattopadhyay and Zuckerman (STOC' 16, Annals of Mathematics' 19) and Li (FOCS' 16). - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k = O(log n) and constant error, matching the parameters of standard extractors by Li (FOCS' 23). Our constructions significantly improve previous results, and the parameters (entropy requirement and error) are the best possible without first improving the constructions of standard extractors. In addition, our improved affine non-malleable extractors give strong lower bounds for a certain kind of read-once linear branching programs, recently introduced by Gryaznov, Pudlák, and Talebanfard (CCC' 22) as a generalization of several well studied computational models. These bounds match the previously best-known average-case hardness results given by Chattopadhyay and Liao (CCC' 23) and Li (FOCS' 23), where the branching program size lower bounds are close to optimal, but the explicit functions we use here are different. Our results also suggest a possible deeper connection between non-malleable extractors and standard ones.
Cite as

Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2024.108,
  author =	{Li, Xin and Zhong, Yan},
  title =	{{Two-Source and Affine Non-Malleable Extractors for Small Entropy}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{108:1--108:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.108},
  URN =		{urn:nbn:de:0030-drops-202512},
  doi =		{10.4230/LIPIcs.ICALP.2024.108},
  annote =	{Keywords: Randomness Extractors, Non-malleable, Two-source, Affine}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.57
Visible Rank and Codes with Locality

Authors: Omar Alrabiah and Venkatesan Guruswami

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

Abstract
We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call visible rank. The locality constraints of a linear code are stipulated by a matrix H of ⋆’s and 0’s (which we call a "stencil"), whose rows correspond to the local parity checks (with the ⋆’s indicating the support of the check). The visible rank of H is the largest r for which there is a r × r submatrix in H with a unique generalized diagonal of ⋆’s. The visible rank yields a field-independent combinatorial lower bound on the rank of H and thus the co-dimension of the code. We point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [Zeev Dvir et al., 2020]. Using this connection and a construction of appropriate stencils, we answer a question posed in [Zeev Dvir et al., 2020] and demonstrate that symmetric spanoid rank cannot improve the currently best known Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-query locally correctable codes (LCCs) of length n. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs. We also study the t-Disjoint Repair Group Property (t-DRGP) of codes where each codeword symbol must belong to t disjoint check equations. It is known that linear codes with 2-DRGP must have co-dimension Ω(√n) (which is matched by a simple product code construction). We show that there are stencils corresponding to 2-DRGP with visible rank as small as O(log n). However, we show the second tensor of any 2-DRGP stencil has visible rank Ω(n), thus recovering the Ω(√n) lower bound for 2-DRGP. For q-LCC, however, the k'th tensor power for k ⩽ n^{o(1)} is unable to improve the Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-LCCs by a polynomial factor.Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.
Cite as

Omar Alrabiah and Venkatesan Guruswami. Visible Rank and Codes with Locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.APPROX/RANDOM.2021.57,
  author =	{Alrabiah, Omar and Guruswami, Venkatesan},
  title =	{{Visible Rank and Codes with Locality}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.57},
  URN =		{urn:nbn:de:0030-drops-147502},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.57},
  annote =	{Keywords: Visible Rank, Stencils, Locality, DRGP Codes, Locally Correctable Codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.41
Matrix Rigidity Depends on the Target Field

Authors: László Babai and Bohdan Kivva

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

Abstract
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.
Cite as

László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.CCC.2021.41,
  author =	{Babai, L\'{a}szl\'{o} and Kivva, Bohdan},
  title =	{{Matrix Rigidity Depends on the Target Field}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{41:1--41:26},
  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.41},
  URN =		{urn:nbn:de:0030-drops-143153},
  doi =		{10.4230/LIPIcs.CCC.2021.41},
  annote =	{Keywords: Matrix rigidity, field extension}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.17
Fourier and Circulant Matrices Are Not Rigid

Authors: Zeev Dvir and Allen Liu

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

Abstract
The concept of matrix rigidity was first introduced by Valiant in [Friedman, 1993]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed in [Friedman, 1993] that rigidity can be used to prove arithmetic circuit lower bounds. In a surprising result, Alman and Williams showed that the (real valued) Hadamard matrix, which was conjectured to be rigid, is actually not very rigid. This line of work was extended by [Dvir and Edelman, 2017] to a family of matrices related to the Hadamard matrix, but over finite fields. In our work, we take another step in this direction and show that for any abelian group G and function f:G - > {C}, the matrix given by M_{xy} = f(x - y) for x,y in G is not rigid. In particular, we get that complex valued Fourier matrices, circulant matrices, and Toeplitz matrices are all not rigid and cannot be used to carry out Valiant’s approach to proving circuit lower bounds. This complements a recent result of Goldreich and Tal [Goldreich and Tal, 2016] who showed that Toeplitz matrices are nontrivially rigid (but not enough for Valiant’s method). Our work differs from previous non-rigidity results in that those works considered matrices whose underlying group of symmetries was of the form {F}_p^n with p fixed and n tending to infinity, while in the families of matrices we study, the underlying group of symmetries can be any abelian group and, in particular, the cyclic group {Z}_N, which has very different structure. Our results also suggest natural new candidates for rigidity in the form of matrices whose symmetry groups are highly non-abelian. Our proof has four parts. The first extends the results of [Josh Alman and Ryan Williams, 2016; Dvir and Edelman, 2017] to generalized Hadamard matrices over the complex numbers via a new proof technique. The second part handles the N x N Fourier matrix when N has a particularly nice factorization that allows us to embed smaller copies of (generalized) Hadamard matrices inside of it. The third part uses results from number theory to bootstrap the non-rigidity for these special values of N and extend to all sufficiently large N. The fourth and final part involves using the non-rigidity of the Fourier matrix to show that the group algebra matrix, given by M_{xy} = f(x - y) for x,y in G, is not rigid for any function f and abelian group G.
Cite as

Zeev Dvir and Allen Liu. Fourier and Circulant Matrices Are Not Rigid. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.CCC.2019.17,
  author =	{Dvir, Zeev and Liu, Allen},
  title =	{{Fourier and Circulant Matrices Are Not Rigid}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{17:1--17:23},
  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.17},
  URN =		{urn:nbn:de:0030-drops-108390},
  doi =		{10.4230/LIPIcs.CCC.2019.17},
  annote =	{Keywords: Rigidity, Fourier matrix, Circulant matrix}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.32
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs

Authors: Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, and Avi Wigderson

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

Abstract
We introduce a simple logical inference structure we call a spanoid (generalizing the notion of a matroid), which captures well-studied problems in several areas. These include combinatorial geometry (point-line incidences), algebra (arrangements of hypersurfaces and ideals), statistical physics (bootstrap percolation), network theory (gossip / infection processes) and coding theory. We initiate a thorough investigation of spanoids, from computational and structural viewpoints, focusing on parameters relevant to the applications areas above and, in particular, to questions regarding Locally Correctable Codes (LCCs). One central parameter we study is the rank of a spanoid, extending the rank of a matroid and related to the dimension of codes. This leads to one main application of our work, establishing the first known barrier to improving the nearly 20-year old bound of Katz-Trevisan (KT) on the dimension of LCCs. On the one hand, we prove that the KT bound (and its more recent refinements) holds for the much more general setting of spanoid rank. On the other hand we show that there exist (random) spanoids whose rank matches these bounds. Thus, to significantly improve the known bounds one must step out of the spanoid framework. Another parameter we explore is the functional rank of a spanoid, which captures the possibility of turning a given spanoid into an actual code. The question of the relationship between rank and functional rank is one of the main questions we raise as it may reveal new avenues for constructing new LCCs (perhaps even matching the KT bound). As a first step, we develop an entropy relaxation of functional rank to create a small constant gap and amplify it by tensoring to construct a spanoid whose functional rank is smaller than rank by a polynomial factor. This is evidence that the entropy method we develop can prove polynomially better bounds than KT-type methods on the dimension of LCCs. To facilitate the above results we also develop some basic structural results on spanoids including an equivalent formulation of spanoids as set systems and properties of spanoid products. We feel that given these initial findings and their motivations, the abstract study of spanoids merits further investigation. We leave plenty of concrete open problems and directions.
Cite as

Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, and Avi Wigderson. Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.ITCS.2019.32,
  author =	{Dvir, Zeev and Gopi, Sivakanth and Gu, Yuzhou and Wigderson, Avi},
  title =	{{Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-101258},
  doi =		{10.4230/LIPIcs.ITCS.2019.32},
  annote =	{Keywords: Locally correctable codes, spanoids, entropy, bootstrap percolation, gossip spreading, matroid, union-closed family}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.20
Outlaw Distributions and Locally Decodable Codes

Authors: Jop Briët, Zeev Dvir, and Sivakanth Gopi

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. Despite decades of study, the optimal trade-off between query complexity and codeword length is far from understood. In this work, we give a new characterization of LDCs using distributions over Boolean functions whose expectation is hard to approximate (in L_\infty norm) with a small number of samples. We coin the term 'outlaw distributions' for such distributions since they 'defy' the Law of Large Numbers. We show that the existence of outlaw distributions over sufficiently 'smooth' functions implies the existence of constant query LDCs and vice versa. We give several candidates for outlaw distributions over smooth functions coming from finite field incidence geometry and from hypergraph (non)expanders. We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters.
Cite as

Jop Briët, Zeev Dvir, and Sivakanth Gopi. Outlaw Distributions and Locally Decodable Codes. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.ITCS.2017.20,
  author =	{Bri\"{e}t, Jop and Dvir, Zeev and Gopi, Sivakanth},
  title =	{{Outlaw Distributions and Locally Decodable Codes}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.20},
  URN =		{urn:nbn:de:0030-drops-81888},
  doi =		{10.4230/LIPIcs.ITCS.2017.20},
  annote =	{Keywords: Locally Decodable Code, VC-dimension, Incidence Geometry, Cayley Hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.15
On the Number of Ordinary Lines Determined by Sets in Complex Space

Authors: Abdul Basit, Zeev Dvir, Shubhangi Saraf, and Charles Wolf

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Kelly's theorem states that a set of n points affinely spanning C^3 must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least 3n/2 ordinary lines, unless the configuration has n-1 points in a plane and one point outside the plane (in which case there are at least n-1 ordinary lines). In addition, when at most n/2 points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with four and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span four or more dimensions, with at most n/2 points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines.
Cite as

Abdul Basit, Zeev Dvir, Shubhangi Saraf, and Charles Wolf. On the Number of Ordinary Lines Determined by Sets in Complex Space. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{basit_et_al:LIPIcs.SoCG.2017.15,
  author =	{Basit, Abdul and Dvir, Zeev and Saraf, Shubhangi and Wolf, Charles},
  title =	{{On the Number of Ordinary Lines Determined by Sets in Complex Space}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.15},
  URN =		{urn:nbn:de:0030-drops-71883},
  doi =		{10.4230/LIPIcs.SoCG.2017.15},
  annote =	{Keywords: Incidences, Combinatorial Geometry, Designs, Polynomial Method}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.29
Sylvester-Gallai for Arrangements of Subspaces

Authors: Zeev Dvir and Guangda Hu

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

Abstract
In this work we study arrangements of k-dimensional subspaces V_1,...,V_n over the complex numbers. Our main result shows that, if every pair V_a, V_b of subspaces is contained in a dependent triple (a triple V_a, V_b, V_c contained in a 2k-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on k (and not on n). The theorem holds under the assumption that the subspaces are pairwise non-intersecting (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kelly's theorem for complex numbers), which proves the k=1 case. Our proof also handles arrangements in which we have many pairs (instead of all) appearing in dependent triples, generalizing the quantitative results of Barak et. al. One of the main ingredients in the proof is a strengthening of a theorem of Barthe (from the k=1 to k>1 case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average. Such a mapping can be found, unless there is an obstruction in the form of a low dimensional subspace intersecting many of the spaces in the arrangement (in which case one can use a different argument to prove the main theorem).
Cite as

Zeev Dvir and Guangda Hu. Sylvester-Gallai for Arrangements of Subspaces. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 29-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.SOCG.2015.29,
  author =	{Dvir, Zeev and Hu, Guangda},
  title =	{{Sylvester-Gallai for Arrangements of Subspaces}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{29--43},
  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.29},
  URN =		{urn:nbn:de:0030-drops-51303},
  doi =		{10.4230/LIPIcs.SOCG.2015.29},
  annote =	{Keywords: Sylvester-Gallai, Locally Correctable Codes}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.584
On the Number of Rich Lines in Truly High Dimensional Sets

Authors: Zeev Dvir and Sivakanth Gopi

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

Abstract
We prove a new upper bound on the number of r-rich lines (lines with at least r points) in a 'truly' d-dimensional configuration of points v_1,...,v_n over the complex numbers. More formally, we show that, if the number of r-rich lines is significantly larger than n^2/r^d then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor r^d can be replaced with a tight r^{d+1}. If true, this would generalize the classic Szemeredi-Trotter theorem which gives a bound of n^2/r^3 on the number of r-rich lines in a planar configuration. This conjecture was shown to hold in R^3 in the seminal work of Guth and Katz and was also recently proved over R^4 (under some additional restrictions) by Solomon and Sharir. For the special case of arithmetic progressions (r collinear points that are evenly distanced) we give a bound that is tight up to lower order terms, showing that a d-dimensional grid achieves the largest number of r-term progressions. The main ingredient in the proof is a new method to find a low degree polynomial that vanishes on many of the rich lines. Unlike previous applications of the polynomial method, we do not find this polynomial by interpolation. The starting observation is that the degree r-2 Veronese embedding takes r-collinear points to r linearly dependent images. Hence, each collinear r-tuple of points, gives us a dependent r-tuple of images. We then use the design-matrix method of Barak et al. to convert these 'local' linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.
Cite as

Zeev Dvir and Sivakanth Gopi. On the Number of Rich Lines in Truly High Dimensional Sets. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 584-598, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.SOCG.2015.584,
  author =	{Dvir, Zeev and Gopi, Sivakanth},
  title =	{{On the Number of Rich Lines in Truly High Dimensional Sets}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{584--598},
  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.584},
  URN =		{urn:nbn:de:0030-drops-51110},
  doi =		{10.4230/LIPIcs.SOCG.2015.584},
  annote =	{Keywords: Incidences, Combinatorial Geometry, Designs, Polynomial Method, Additive Combinatorics}
}
  • Refine by Author
  • 6 Dvir, Zeev
  • 3 Gopi, Sivakanth
  • 2 Saraf, Shubhangi
  • 1 Alrabiah, Omar
  • 1 Babai, László
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Error-correcting codes
  • 3 Theory of computation → Pseudorandomness and derandomization
  • 2 Theory of computation
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Algebraic complexity theory
  • Show More...

  • Refine by Keyword
  • 2 Combinatorial Geometry
  • 2 Designs
  • 2 Incidences
  • 2 Locally Correctable Codes
  • 2 Polynomial Method
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 6 2024
  • 2 2015
  • 2 2017
  • 2 2019
  • 2 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact