Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REPRESENTATIONS OF THE SYMMETRIC GROUP:
Reports tagged with representations of the symmetric group:
TR94-014 | 12th December 1994
Miklos Ajtai

#### The Independence of the modulo p Counting Principles

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 >>>

TR94-015 | 12th December 1994
Miklos Ajtai

#### Symmetric Systems of Linear Equations modulo \$p\$

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 >>>

TR16-162 | 18th October 2016
Joshua Grochow

#### NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

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 >>>

ISSN 1433-8092 | Imprint