Search Results

Documents authored by Ta-Shma, Amnon

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.36
Simplifying Armoni’s PRG

Authors: Ben Chen and Amnon Ta-Shma

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

Abstract
We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni’s PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be obtained as simple variants of INW. For the construction to work we need space-efficient extractors with tiny entropy loss. We use the extractors from [Chattopadhyay and Liao, 2020] instead of [Guruswami et al., 2009] taking advantage of the very high min-entropy regime we work with. We remark that using these extractors has the additional benefit of making the dependence on the branching program alphabet Σ correct.
Cite as

Ben Chen and Amnon Ta-Shma. Simplifying Armoni’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 36:1-36:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.36,
  author =	{Chen, Ben and Ta-Shma, Amnon},
  title =	{{Simplifying Armoni’s PRG}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{36:1--36:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  URN =		{urn:nbn:de:0030-drops-244024},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  annote =	{Keywords: PRG, ROBP, read-once, random, psuedorandom, armoni, derandomization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.31
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

Authors: Amnon Ta-Shma and Ron Zadicario

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

Abstract
Numerous works have studied the probability that a length t-1 random walk on an expander is confined to a given rectangle S_1 × … × S_t, providing both upper and lower bounds for this probability. However, when the densities of the sets S_i may depend on the walk length (e.g., when all set are equal and the density is 1-1/t), the currently best known upper and lower bounds are very far from each other. We give an improved confinement lower bound that almost matches the upper bound. We also study the more general question, of how well random walks fool various classes of test functions. Recently, Golowich and Vadhan proved that random walks on λ-expanders fool Boolean, symmetric functions up to a O(λ) error in total variation distance, with no dependence on the labeling bias. Our techniques extend this result to cases not covered by it, e.g., to functions testing confinement to S_1 × … × S_t, where each set S_i either has density ρ or 1-ρ, for arbitrary ρ. Technique-wise, we extend Beck’s framework for analyzing what is often referred to as the "flow" of linear operators, reducing it to bounding the entries of a product of 2×2 matrices.
Cite as

Amnon Ta-Shma and Ron Zadicario. The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tashma_et_al:LIPIcs.APPROX/RANDOM.2024.31,
  author =	{Ta-Shma, Amnon and Zadicario, Ron},
  title =	{{The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-210246},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.31},
  annote =	{Keywords: Expander random walks, Expander hitting property}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CCC.2023
LIPIcs, Volume 264, CCC 2023, Complete Volume

Authors: Amnon Ta-Shma

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
LIPIcs, Volume 264, CCC 2023, Complete Volume
Cite as

38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 1-936, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{tashma:LIPIcs.CCC.2023,
  title =	{{LIPIcs, Volume 264, CCC 2023, Complete Volume}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{1--936},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023},
  URN =		{urn:nbn:de:0030-drops-182690},
  doi =		{10.4230/LIPIcs.CCC.2023},
  annote =	{Keywords: LIPIcs, Volume 264, CCC 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CCC.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Amnon Ta-Shma

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tashma:LIPIcs.CCC.2023.0,
  author =	{Ta-Shma, Amnon},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.0},
  URN =		{urn:nbn:de:0030-drops-182703},
  doi =		{10.4230/LIPIcs.CCC.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.11
Improved Local Testing for Multiplicity Codes

Authors: Dan Karliner and Amnon Ta-Shma

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

Abstract
Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in 𝔽_p^m. Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing. Recently, [Karliner et al., 2022] showed that the plane test, which tests the degree of the codeword on a random plane, is a good local tester for small enough degrees. In this work we simplify and extend the analysis of local testing for multiplicity codes, giving a more general and tight analysis. In particular, we show that multiplicity codes MRM_p(m, d, s) over prime fields with arbitrary d are locally testable by an appropriate k-flat test, which tests the degree of the codeword on a random k-dimensional affine subspace. The relationship between the degree parameter d and the required dimension k is shown to be nearly optimal, and improves on [Karliner et al., 2022] in the case of planes. Our analysis relies on a generalization of the technique of canonincal monomials introduced in [Haramaty et al., 2013]. Generalizing canonical monomials to the multiplicity case requires substantially different proofs which exploit the algebraic structure of multiplicity codes.
Cite as

Dan Karliner and Amnon Ta-Shma. Improved Local Testing for Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{karliner_et_al:LIPIcs.APPROX/RANDOM.2022.11,
  author =	{Karliner, Dan and Ta-Shma, Amnon},
  title =	{{Improved Local Testing for Multiplicity Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.11},
  URN =		{urn:nbn:de:0030-drops-171339},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.11},
  annote =	{Keywords: local testing, multiplicity codes, Reed Muller codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.12
Unbalanced Expanders from Multiplicity Codes

Authors: Itay Kalev and Amnon Ta-Shma

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

Abstract
In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions. We give an alternative construction that is based on Multiplicity codes. While the bottom-line result is similar to the GUV result, the analysis is very different. In GUV (and Parvaresh-Vardy codes) the polynomial ring is closed to a finite field, and every polynomial is associated with related elements in the finite field. In our construction a polynomial from the polynomial ring is associated with its iterated derivatives. Our analysis boils down to solving a differential equation over a finite field, and uses previous techniques, introduced by Kopparty (in [Swastik Kopparty, 2015]) for the list-decoding setting. We also observe that these (and more general) questions were studied in differential algebra, and we use the terminology and result developed there. We believe these techniques have the potential of getting better constructions and solving the current bottlenecks in the area.
Cite as

Itay Kalev and Amnon Ta-Shma. Unbalanced Expanders from Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kalev_et_al:LIPIcs.APPROX/RANDOM.2022.12,
  author =	{Kalev, Itay and Ta-Shma, Amnon},
  title =	{{Unbalanced Expanders from Multiplicity Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.12},
  URN =		{urn:nbn:de:0030-drops-171346},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.12},
  annote =	{Keywords: Condensers, Multiplicity codes, Differential equations}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.14
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.43
Expander Random Walks: The General Case and Limitations

Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.
Cite as

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43,
  author =	{Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon},
  title =	{{Expander Random Walks: The General Case and Limitations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43},
  URN =		{urn:nbn:de:0030-drops-163849},
  doi =		{10.4230/LIPIcs.ICALP.2022.43},
  annote =	{Keywords: Expander Graphs, Random Walks, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.22
Error Reduction for Weighted PRGs Against Read Once Branching Programs

Authors: Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma

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

Abstract
Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [Braverman et al., 2020], are a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered, rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and Liao [Eshan Chattopadhyay and Jyun-Jie Liao, 2020] somewhat simplified the technically involved BCG construction, also obtaining some improvement in parameters. In this work we devise an error reduction procedure for PRGs against ROBPs. More precisely, our procedure transforms any PRG against length n width w ROBP with error 1/poly(n) having seed length s to a WPRG with seed length s + O(logw/(ε) ⋅ log log1/(ε)). By instantiating our procedure with Nisan’s PRG [Noam Nisan, 1992] we obtain a WPRG with seed length O(log{n} ⋅ log(nw) + logw/(ε) ⋅ log log 1/(ε)). This improves upon [Braverman et al., 2020] and is incomparable with [Eshan Chattopadhyay and Jyun-Jie Liao, 2020]. Our construction is significantly simpler on the technical side and is conceptually cleaner. Another advantage of our construction is its low space complexity O(log{nw})+poly(log log1/(ε)) which is logarithmic in n for interesting values of the error parameter ε. Previous constructions (like [Braverman et al., 2020; Eshan Chattopadhyay and Jyun-Jie Liao, 2020]) specify the seed length but not the space complexity, though it is plausible they can also achieve such (or close) space complexity.
Cite as

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2021.22,
  author =	{Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon},
  title =	{{Error Reduction for Weighted PRGs Against Read Once Branching Programs}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{22:1--22:17},
  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.22},
  URN =		{urn:nbn:de:0030-drops-142963},
  doi =		{10.4230/LIPIcs.CCC.2021.22},
  annote =	{Keywords: Pseudorandom generators, Read once branching programs, Space-bounded computation}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.7
On Hitting-Set Generators for Polynomials That Vanish Rarely

Authors: Dean Doron, Amnon Ta-Shma, and Roei Tell

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

Abstract
The problem of constructing hitting-set generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it easier to construct a hitting-set generator for polynomials p: 𝔽ⁿ → 𝔽 of degree d if we are guaranteed that the polynomial vanishes on at most an ε > 0 fraction of its inputs? We will specifically be interested in tiny values of ε≪ d/|𝔽|. This question was first considered by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for a particular application, and another specific setting was later studied by the third author (CCC 2017). In this work our main interest is a systematic study of the relaxed problem, in its general form, and we prove results that significantly improve and extend the two previously-known results. Our contributions are of two types: - Over fields of size 2 ≤ |𝔽| ≤ poly(n), we show that the seed length of any hitting-set generator for polynomials of degree d ≤ n^{.49} that vanish on at most ε = |𝔽|^{-t} of their inputs is at least Ω((d/t)⋅log(n)). - Over 𝔽₂, we show that there exists a (non-explicit) hitting-set generator for polynomials of degree d ≤ n^{.99} that vanish on at most ε = |𝔽|^{-t} of their inputs with seed length O((d-t)⋅log(n)). We also show a polynomial-time computable hitting-set generator with seed length O((d-t)⋅(2^{d-t}+log(n))). In addition, we prove that the problem we study is closely related to the following question: "Does there exist a small set S ⊆ 𝔽ⁿ whose degree-d closure is very large?", where the degree-d closure of S is the variety induced by the set of degree-d polynomials that vanish on S.
Cite as

Dean Doron, Amnon Ta-Shma, and Roei Tell. On Hitting-Set Generators for Polynomials That Vanish Rarely. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2020.7,
  author =	{Doron, Dean and Ta-Shma, Amnon and Tell, Roei},
  title =	{{On Hitting-Set Generators for Polynomials That Vanish Rarely}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{7:1--7:23},
  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.7},
  URN =		{urn:nbn:de:0030-drops-126109},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.7},
  annote =	{Keywords: Hitting-set generators, Polynomials over finite fields, Quantified derandomization}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.1
Near-Optimal Erasure List-Decodable Codes

Authors: Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
A code 𝒞 ⊆ {0,1}^n̅ is (s,L) erasure list-decodable if for every word w, after erasing any s symbols of w, the remaining n̅-s symbols have at most L possible completions into a codeword of 𝒞. Non-explicitly, there exist binary ((1-τ)n̅,L) erasure list-decodable codes with rate approaching τ and tiny list-size L = O(log 1/(τ)). Achieving either of these parameters explicitly is a natural open problem (see, e.g., [Guruswami and Indyk, 2002; Guruswami, 2003; Guruswami, 2004]). While partial progress on the problem has been achieved, no prior nontrivial explicit construction achieved rate better than Ω(τ²) or list-size smaller than Ω(1/τ). Furthermore, Guruswami showed no linear code can have list-size smaller than Ω(1/τ) [Guruswami, 2003]. We construct an explicit binary ((1-τ)n̅,L) erasure list-decodable code having rate τ^(1+γ) (for any constant γ > 0 and small τ) and list-size poly(log 1/τ), answering simultaneously both questions, and exhibiting an explicit non-linear code that provably beats the best possible linear code. The binary erasure list-decoding problem is equivalent to the construction of explicit, low-error, strong dispersers outputting one bit with minimal entropy-loss and seed-length. For error ε, no prior explicit construction achieved seed-length better than 2log(1/ε) or entropy-loss smaller than 2log(1/ε), which are the best possible parameters for extractors. We explicitly construct an ε-error one-bit strong disperser with near-optimal seed-length (1+γ)log(1/ε) and entropy-loss O(log log1/ε). The main ingredient in our construction is a new (and almost-optimal) unbalanced two-source extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny min-entropy O(log log n) and the other source has length O(log n) and arbitrarily small constant min-entropy rate. When instantiated as a balanced two-source extractor, it improves upon Raz’s extractor [Raz, 2005] in the constant error regime. The construction incorporates recent components and ideas from extractor theory with a delicate and novel analysis needed in order to solve dependency and error issues that prevented previous papers (such as [Li, 2015; Chattopadhyay and Zuckerman, 2019; Cohen, 2016]) from achieving the above results.
Cite as

Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 1:1-1:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.CCC.2020.1,
  author =	{Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon},
  title =	{{Near-Optimal Erasure List-Decodable Codes}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{1:1--1:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.1},
  URN =		{urn:nbn:de:0030-drops-125531},
  doi =		{10.4230/LIPIcs.CCC.2020.1},
  annote =	{Keywords: Dispersers, Erasure codes, List decoding, Ramsey graphs, Two-source extractors}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.43
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

Authors: Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma

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

Abstract
In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error epsilon for n-bit sources having min-entropy {polylog}(n/epsilon). Unfortunately, the construction’s running-time is {poly}(n/epsilon), which means that with polynomial-time constructions, only polynomially-small errors are possible. Our main result is a {poly}(n,log(1/epsilon))-time computable two-source condenser. For any k >= {polylog}(n/epsilon), our condenser transforms two independent (n,k)-sources to a distribution over m = k-O(log(1/epsilon)) bits that is epsilon-close to having min-entropy m - o(log(1/epsilon)). Hence, achieving entropy gap of o(log(1/epsilon)). The bottleneck for obtaining low error in recent constructions of two-source extractors lies in the use of resilient functions. Informally, this is a function that receives input bits from r players with the property that the function’s output has small bias even if a bounded number of corrupted players feed adversarial inputs after seeing the inputs of the other players. The drawback of using resilient functions is that the error cannot be smaller than ln r/r. This, in return, forces the running time of the construction to be polynomial in 1/epsilon. A key component in our construction is a variant of resilient functions which we call entropy-resilient functions. This variant can be seen as playing the above game for several rounds, each round outputting one bit. The goal of the corrupted players is to reduce, with as high probability as they can, the min-entropy accumulated throughout the rounds. We show that while the bias decreases only polynomially with the number of players in a one-round game, their success probability decreases exponentially in the entropy gap they are attempting to incur in a repeated game.
Cite as

Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43,
  author =	{Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon},
  title =	{{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{43:1--43:20},
  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.43},
  URN =		{urn:nbn:de:0030-drops-112587},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.43},
  annote =	{Keywords: Condensers, Extractors, Resilient functions, Explicit constructions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.3
A New Approach for Constructing Low-Error, Two-Source Extractors

Authors: Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
Our main contribution in this paper is a new reduction from explicit two-source extractors for polynomially-small entropy rate and negligible error to explicit t-non-malleable extractors with seed-length that has a good dependence on t. Our reduction is based on the Chattopadhyay and Zuckerman framework (STOC 2016), and surprisingly we dispense with the use of resilient functions which appeared to be a major ingredient there and in follow-up works. The use of resilient functions posed a fundamental barrier towards achieving negligible error, and our new reduction circumvents this bottleneck. The parameters we require from t-non-malleable extractors for our reduction to work hold in a non-explicit construction, but currently it is not known how to explicitly construct such extractors. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. Nonetheless, we believe our work gives a viable approach for solving the important problem of low-error two-source extractors. Furthermore, our work highlights an existing barrier in constructing low-error two-source extractors, and draws attention to the dependence of the parameter t in the seed-length of the non-malleable extractor. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.
Cite as

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma. A New Approach for Constructing Low-Error, Two-Source Extractors. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.CCC.2018.3,
  author =	{Ben-Aroya, Avraham and Chattopadhyay, Eshan and Doron, Dean and Li, Xin and Ta-Shma, Amnon},
  title =	{{A New Approach for Constructing Low-Error, Two-Source Extractors}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.3},
  URN =		{urn:nbn:de:0030-drops-88877},
  doi =		{10.4230/LIPIcs.CCC.2018.3},
  annote =	{Keywords: Two-Source Extractors, Non-Malleable Extractors, Pseudorandomness, Explicit Constructions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.41
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers

Authors: Dean Doron, François Le Gall, and Amnon Ta-Shma

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

Abstract
A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx=b, where L is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem. Surprisingly we are able to show a probabilistic, logspace algorithm solving the problem. We further extend the algorithm to other families of graphs like Eulerian graphs (and directed regular graphs) and graphs that mix in polynomial time. Our approach is to pseudo-invert the Laplacian, by first "peeling-off" the problematic kernel of the operator, and then to approximate the inverse of the remaining part by using a Taylor series. We approximate the Taylor series using a previous work and the special structure of the problem. For directed graphs we exploit in the analysis the Jordan normal form and results from matrix functions.
Cite as

Dean Doron, François Le Gall, and Amnon Ta-Shma. Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX-RANDOM.2017.41,
  author =	{Doron, Dean and Le Gall, Fran\c{c}ois and Ta-Shma, Amnon},
  title =	{{Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.41},
  URN =		{urn:nbn:de:0030-drops-75908},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.41},
  annote =	{Keywords: Laplacian solvers, Randomized logspace, Bounded-space complexity classes, Random walks, Matrix computation}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.327
The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent

Authors: Efraim Gelman and Amnon Ta-Shma

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
A switching network of depth d is a layered graph with d layers and n vertices in each layer. The edges of the switching network do not cross between layers and in each layer the edges form a partial matching. A switching network defines a stochastic process over Sn that starts with the identity permutation and goes through the layers of the network from first to last, where for each layer and each pair (i,j) in the partial matching of the layer, it applies the transposition (i j) with probability half. A switching network is good if the final distribution is close to the uniform distribution over S_n. A switching network is epsilon-almost q-permutation-wise independent if its action on any ordered set of size q is almost uniform, and is epsilon-almost q-set-wise independent if its action on any set of size q is almost uniform. Mixing of switching networks (even for q-permutation-wise and q-set-wise independence) has found several applications, mostly in cryptography. Some applications further require some additional properties from the network, e.g., the existence of an algorithm that given a permutation can set the switches such that the network generates the given permutation, a property that the Benes network has. Morris, Rogaway and Stegers showed the Thorp shuffle (which corresponds to applying two or more butterflies one after the other) is q-permutation-wise independent, for q=n^gamma for gamma that depends on the number of sequential applications of the butterfly network. The techniques applied by Morris et al. do not seem to apply for the Benes network. In this work we show the Benes network is almost q-set-wise independent for q up to about sqrt(n). Our technique is simple and completely new, and we believe carries hope for getting even better results in the future.
Cite as

Efraim Gelman and Amnon Ta-Shma. The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 327-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gelman_et_al:LIPIcs.FSTTCS.2014.327,
  author =	{Gelman, Efraim and Ta-Shma, Amnon},
  title =	{{The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{327--338},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.327},
  URN =		{urn:nbn:de:0030-drops-48538},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.327},
  annote =	{Keywords: switching network, mixing, Benes}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact