9 Search Results for "Ben-Shachar, Gil"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.54
Candidate Tree Codes via Pascal Determinant Cubes

Authors: Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan

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

Abstract
Tree codes are combinatorial structures introduced by Schulman [Schulman, 1993] as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining tree code property requires structure that remains elusive. To the best of our knowledge, only one candidate appears in the literature, due to Moore and Schulman [Moore and Schulman, 2014]. We put forth a new candidate for an explicit asymptotically-good tree code. Our construction is an extension of the vanishing rate tree code by Cohen-Haeupler-Schulman [Cohen et al., 2018], and its correctness relies on a conjecture that we introduce on certain Pascal determinants indexed by the points of the Boolean hypercube. Furthermore, using the vanishing distance tree code by Gelles et al. [Gelles et al., 2016] enables us to present a construction that relies on an even weaker assumption. We furnish evidence supporting our conjecture through numerical computation, combinatorial arguments from planar path graphs and based on well-studied heuristics from arithmetic geometry.
Cite as

Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan. Candidate Tree Codes via Pascal Determinant Cubes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2021.54,
  author =	{Ben Yaacov, Inbar and Cohen, Gil and Narayanan, Anand Kumar},
  title =	{{Candidate Tree Codes via Pascal Determinant Cubes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{54:1--54:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.54},
  URN =		{urn:nbn:de:0030-drops-147474},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.54},
  annote =	{Keywords: Tree codes, Sparse polynomials, Explicit constructions}
}
Document
Crazy New Idea
DOI: 10.4230/OASIcs.LDK.2021.4
A Computational Simulation of Children’s Language Acquisition (Crazy New Idea)

Authors: Ben Ambridge

Published in: OASIcs, Volume 93, 3rd Conference on Language, Data and Knowledge (LDK 2021)

Abstract
Many modern NLP models are already close to simulating children’s language acquisition; the main thing they currently lack is a "real world" representation of semantics that allows them to map from form to meaning and vice-versa. The aim of this "Crazy Idea" is to spark a discussion about how we might get there.
Cite as

Ben Ambridge. A Computational Simulation of Children’s Language Acquisition (Crazy New Idea). In 3rd Conference on Language, Data and Knowledge (LDK 2021). Open Access Series in Informatics (OASIcs), Volume 93, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ambridge:OASIcs.LDK.2021.4,
  author =	{Ambridge, Ben},
  title =	{{A Computational Simulation of Children’s Language Acquisition}},
  booktitle =	{3rd Conference on Language, Data and Knowledge (LDK 2021)},
  pages =	{4:1--4:3},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-199-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{93},
  editor =	{Gromann, Dagmar and S\'{e}rasset, Gilles and Declerck, Thierry and McCrae, John P. and Gracia, Jorge and Bosque-Gil, Julia and Bobillo, Fernando and Heinisch, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2021.4},
  URN =		{urn:nbn:de:0030-drops-145402},
  doi =		{10.4230/OASIcs.LDK.2021.4},
  annote =	{Keywords: Child language acquisition, language development, deep learning, BERT, ELMo, GPT-3}
}
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-dev.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.2019.9
Typically-Correct Derandomization for Small Time and Space

Authors: William M. Hoza

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

Abstract
Suppose a language L can be decided by a bounded-error randomized algorithm that runs in space S and time n * poly(S). We give a randomized algorithm for L that still runs in space O(S) and time n * poly(S) that uses only O(S) random bits; our algorithm has a low failure probability on all but a negligible fraction of inputs of each length. As an immediate corollary, there is a deterministic algorithm for L that runs in space O(S) and succeeds on all but a negligible fraction of inputs of each length. We also give several other complexity-theoretic applications of our technique.
Cite as

William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hoza:LIPIcs.CCC.2019.9,
  author =	{Hoza, William M.},
  title =	{{Typically-Correct Derandomization for Small Time and Space}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{9:1--9:39},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9},
  URN =		{urn:nbn:de:0030-drops-108317},
  doi =		{10.4230/LIPIcs.CCC.2019.9},
  annote =	{Keywords: Derandomization, pseudorandomness, space complexity}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2019.64
Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition)

Authors: Gill Barequet and Gil Ben-Shachar

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
In this video, we survey some results concerning polyominoes, which are sets of connected cells on the square lattice, and specifically, minimal-perimeter polyominoes, that are polyominoes with the minimal-perimeter from all polyominoes of the same size.
Cite as

Gill Barequet and Gil Ben-Shachar. Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.64,
  author =	{Barequet, Gill and Ben-Shachar, Gil},
  title =	{{Properties of Minimal-Perimeter Polyominoes}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{64:1--64:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.64},
  URN =		{urn:nbn:de:0030-drops-104687},
  doi =		{10.4230/LIPIcs.SoCG.2019.64},
  annote =	{Keywords: Polyominoes, Perimeter, Minimal-Perimeter}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.34
Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log (W/epsilon)) lower bound for RW epsilon additive approximations and a Omega(log (W/epsilon)+log log R) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^(-1) log(RW)log log (RW)) space and performs updates in O(log (RW)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Give Me Some Slack: Efficient Network Measurements. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.MFCS.2018.34,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.34},
  URN =		{urn:nbn:de:0030-drops-96165},
  doi =		{10.4230/LIPIcs.MFCS.2018.34},
  annote =	{Keywords: Streaming, Network Measurements, Statistics, Lower Bounds}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.163
Brief Announcement: Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of our paper [{Ben Basat} et al., 2017] is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log{R}) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log ({W/epsilon})) lower bound for RW epsilon additive approximations and a Omega(log ({W/epsilon})+log log{R}) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^{-1} log ({RW})log log ({RW})) space and performs updates in O(log ({RW})) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Brief Announcement: Give Me Some Slack: Efficient Network Measurements. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 163:1-163:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ICALP.2018.163,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Brief Announcement: Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{163:1--163:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.163},
  URN =		{urn:nbn:de:0030-drops-91672},
  doi =		{10.4230/LIPIcs.ICALP.2018.163},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.11
Efficient Summing over Sliding Windows

Authors: Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of Omega(1/epsilon + log(W)) memory bits for Wepsilon-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/epsilon + log(W)) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0, 1, ..., R}, is addressed. The paper shows that approximating the sum within an additive error of RW epsilon can also be done using Theta(1/epsilon + log(W)) bits for epsilon = Omega(1/W). For epsilon = o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B = Theta(W*log(1/(W*epsilon))) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time.
Cite as

Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient Summing over Sliding Windows. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.SWAT.2016.11,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy and Kassner, Yaron},
  title =	{{Efficient Summing over Sliding Windows}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.11},
  URN =		{urn:nbn:de:0030-drops-60241},
  doi =		{10.4230/LIPIcs.SWAT.2016.11},
  annote =	{Keywords: Streaming, Statistics, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.680
Two Structural Results for Low Degree Polynomials and Applications

Authors: Gil Cohen and Avishay Tal

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

Abstract
In this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field F, for any polynomial f on n variables with degree d > log(n)/10, there exists a subspace of F^n with dimension at least d n^(1/(d-1)) on which f is constant. This result is shown to be tight. Stated differently, a degree d polynomial cannot compute an affine disperser for dimension smaller than the stated dimension. Using a recursive argument, we obtain our second structural result, showing that any degree d polynomial f induces a partition of F^n to affine subspaces of dimension n^(1/(d-1)!), such that f is constant on each part. We extend both structural results to more than one polynomial. We further prove an analog of the first structural result to sparse polynomials (with no restriction on the degree) and to functions that are close to low degree polynomials. We also consider the algorithmic aspect of the two structural results. Our structural results have various applications, two of which are: * Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over any finite field any affine extractor is also an extractor for varieties with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over the binary field. * Ben-Sasson and Kopparty [SIAM J. C 2012] proved that any degree 3 affine disperser over a prime field is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.
Cite as

Gil Cohen and Avishay Tal. Two Structural Results for Low Degree Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 680-709, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2015.680,
  author =	{Cohen, Gil and Tal, Avishay},
  title =	{{Two Structural Results for Low Degree Polynomials and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{680--709},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.680},
  URN =		{urn:nbn:de:0030-drops-53307},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.680},
  annote =	{Keywords: low degree polynomials, affine extractors, affine dispersers, extractors for varieties, dispersers for varieties}
}
  • Refine by Author
  • 3 Ben Basat, Ran
  • 3 Cohen, Gil
  • 3 Einziger, Gil
  • 3 Friedman, Roy
  • 1 Ambridge, Ben
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Pseudorandomness and derandomization
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Networks → Network measurement
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Error-correcting codes
  • Show More...

  • Refine by Keyword
  • 3 Streaming
  • 2 Explicit constructions
  • 2 Lower Bounds
  • 2 Statistics
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2019
  • 2 2018
  • 2 2021
  • 1 2015
  • 1 2016

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