We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. This ... more >>>

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with ... more >>>

A new notion of predictive complexity and corresponding amount of
information are considered.
Predictive complexity is a generalization of Kolmogorov complexity
which bounds the ability of any algorithm to predict elements of
a sequence of outcomes. We consider predictive complexity for a wide class
of bounded loss functions which ... more >>>

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly ... more >>>

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>