Next

__
TR23-085
| 4th June 2023
__

Ari Karchmer#### Average-Case PAC-Learning from Nisan's Natural Proofs

__
TR23-084
| 31st May 2023
__

Itai Dinur#### Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model

__
TR23-083
| 2nd June 2023
__

Srinivasan A, Uma Girish#### Trade-offs between Entanglement and Communication

Next

Ari Karchmer

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds imply algorithms for learning circuits with membership queries over the uniform distribution. Indeed, they exercised this implication to obtain a quasi-polynomial time learning algorithm for ${AC}^0[p]$ circuits, for any prime $p$, by leveraging the existing natural proofs from ... more >>>

Itai Dinur

The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length $T$ and width $2^{S}$ attempts to compute a function $f:\{0,1\}^n \rightarrow \{0,1 \}$. However, instead of receiving direct access to the input bits ... more >>>

Srinivasan A, Uma Girish

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. ... more >>>

Next