Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SANKEERTH RAO:
All reports by Author Sankeerth Rao:

TR18-076 | 22nd April 2018
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 2

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 approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>


TR17-070 | 15th April 2017
Shachar Lovett, Sankeerth Rao, Alex Vardy

Probabilistic Existence of Large Sets of Designs

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>


TR17-033 | 19th February 2017
Daniel Kane, Shachar Lovett, Sankeerth Rao

Labeling the complete bipartite graph with no zero cycles

Revisions: 2

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>>




ISSN 1433-8092 | Imprint