All reports by Author Srinivasan Arunachalam:

__
TR21-013
| 20th January 2021
__

Srinivasan Arunachalam, Penghui Yao#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

__
TR20-185
| 1st December 2020
__

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram#### Quantum learning algorithms imply circuit lower bounds

__
TR19-041
| 7th March 2019
__

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram#### Quantum hardness of learning shallow classical circuits

__
TR18-167
| 25th September 2018
__

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf#### Improved bounds on Fourier entropy and Min-entropy

Srinivasan Arunachalam, Penghui Yao

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>