All reports by Author Vinayak Kumar:

__
TR24-130
| 30th August 2024
__

Sabee Grewal, Vinayak Kumar#### Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits

__
TR23-154
| 12th October 2023
__

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer#### On the Rational Degree of Boolean Functions and Applications

__
TR23-093
| 29th June 2023
__

Vinayak Kumar, Geoffrey Mon#### Relaxed Local Correctability from Local Testing

Revisions: 1

__
TR23-045
| 13th April 2023
__

Vinayak Kumar#### Tight Correlation Bounds for Circuits Between AC0 and TC0

Revisions: 1

__
TR20-151
| 8th October 2020
__

Venkatesan Guruswami, Vinayak Kumar#### Pseudobinomiality of the Sticky Random Walk

Sabee Grewal, Vinayak Kumar

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss ... more >>>

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>

Vinayak Kumar, Geoffrey Mon

We cement the intuitive connection between relaxed local correctability and local testing by presenting a concrete framework for building a relaxed locally correctable code from any family of linear locally testable codes with sufficiently high rate. When instantiated using the locally testable codes of Dinur et al. (STOC 2022), this ... more >>>

Vinayak Kumar

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ ... more >>>

Venkatesan Guruswami, Vinayak Kumar

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>