All reports by Author Joshua Cook:

__
TR24-032
| 22nd February 2024
__

Joshua Cook, Dana Moshkovitz#### Explicit Time and Space Efficient Encoders Exist Only With Random Access

__
TR23-097
| 2nd July 2023
__

Joshua Cook, Ron D. Rothblum#### Efficient Interactive Proofs for Non-Deterministic Bounded Space

Revisions: 1

__
TR22-093
| 28th June 2022
__

Joshua Cook#### More Verifier Efficient Interactive Protocols For Bounded Space

Revisions: 4

__
TR22-014
| 8th February 2022
__

Joshua Cook, Dana Moshkovitz#### Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

Revisions: 2

__
TR20-122
| 8th August 2020
__

Joshua Cook#### Size Bounds on Low Depth Circuits for Promise Majority

Revisions: 3

Joshua Cook, Dana Moshkovitz

We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes ... more >>>

Joshua Cook, Ron D. Rothblum

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>

Joshua Cook

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

Joshua Cook, Dana Moshkovitz

We prove for some constant $a > 1$, for all $k \leq a$,

$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$

for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:

$$\mathbf{MATIME}[n^{c k}] / 1 ...
more >>>

Joshua Cook

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>