The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in ... more >>>

We initiate a study of learning and testing dynamic environments,
focusing on environment that evolve according to a fixed local rule.
The (proper) learning task consists of obtaining the initial configuration
of the environment, whereas for non-proper learning it suffices to predict
its future values. The testing task consists of ... more >>>

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound
for a model of 2-register straight-line programs (SLPs) which is a universal model
of computation (unlike width-2 algebraic branching programs that ... more >>>