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

__
TR17-070
| 15th April 2017
__

Shachar Lovett, Sankeerth Rao, Alex Vardy#### Probabilistic Existence of Large Sets of Designs

__
TR17-033
| 19th February 2017
__

Daniel Kane, Shachar Lovett, Sankeerth Rao#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

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 >>>

Shachar Lovett, Sankeerth Rao, Alex Vardy

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 >>>

Daniel Kane, Shachar Lovett, Sankeerth Rao

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 >>>