We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any \ell disjoint source-sink pairs
on the directed hypercube ... more >>>

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function f:\{0,1\}^n \to \{0,1\}, block sensitivity of f is polynomially related to sensitivity of f (denoted by \mathbf{sens}(f)). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>>

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly(s)-time blackbox ... more >>>

In this work we study oblivious complexity classes. Among our results:
1) For each k \in \mathbb{N}, we construct an explicit language L_k \in O_2P that cannot be computed by circuits of size n^k.
2) We prove a hierarchy theorem for O_2TIME. In particular, for any function t:\mathbb{N} \rightarrow \mathbb{N} ... more >>>