Miklos Ajtai

The modulo $p$ counting principle is a first-order axiom

schema saying that it is possible to count modulo $p$ the number of

elements of the first-order definable subsets of the universe (and of

the finite Cartesian products of the universe with itself) in a

consistent way. It trivially holds on ...
more >>>

Miklos Ajtai

Suppose that $p$ is a prime number $A$ is a finite set

with $n$ elements

and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the

elements of

$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an

$n$ is sufficiently large.) We will ...
more >>>

Joshua Grochow

Mahaney's Theorem states that, assuming P $\neq$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>