42 citations · 46 across the 4 of their papers we have counts for
5 papers
Communication and Memory Efficient Testing of Discrete Distributions
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane +1
We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize…
Torus polynomials: an algebraic approach to ACC lower bounds
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett +1
We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based app…
Probabilistic Existence of Large Sets of Designs
Shachar Lovett, Sankeerth Rao, Alexander Vardy
A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been recentlyintroduced by Kuperberg, Lovett, and Peled (STOC 2012). Us…
The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
Daniel Kane, Shachar Lovett, Sankeerth Rao
Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan…
Lower Bound on the Redundancy of PIR Codes
Sankeerth Rao, Alexander Vardy
We prove that the redundancy of a -server PIR code of dimension is for all . This coincides with a known upper bound of on the redundanc…