Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander Razborov:

TR21-074 | 3rd June 2021
Theodoros Papamakarios, Alexander Razborov

Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

We identify two new big clusters of proof complexity measures equivalent up to
polynomial and $\log n$ factors. The first cluster contains, among others,
the logarithm of tree-like resolution size, regularized (that is, multiplied
by the logarithm of proof length) clause and monomial space, and clause
space, both ordinary and ... more >>>

TR16-184 | 16th November 2016
Alexander Razborov

On Space and Depth in Resolution

We show that the total space in resolution, as well as in any other reasonable
proof system, is equal (up to a polynomial and $(\log n)^{O(1)}$ factors) to
the minimum refutation depth. In particular, all these variants of total space
are equivalent in this sense. The same conclusion holds for ... more >>>

TR16-010 | 28th January 2016
Alexander Razborov

On the Width of Semi-Algebraic Proofs and Algorithms

In this paper we initiate the study of width in semi-algebraic proof systems
and various cut-based procedures in integer programming. We focus on two
important systems: Gomory-Chv\'atal cutting planes and
Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for
proving width lower bounds and apply them to random $k$-CNFs and several ... more >>>

TR15-033 | 6th March 2015
Alexander Razborov

An Ultimate Trade-Off in Propositional Proof Complexity

Revisions: 1

We exhibit an unusually strong trade-off between resolution proof width and tree-like proof size. Namely, we show that for any parameter $k=k(n)$ there are unsatisfiable $k$-CNFs that possess refutations of width $O(k)$, but such that any tree-like refutation of width $n^{1-\epsilon}/k$ must necessarily have {\em double} exponential size $\exp(n^{\Omega(k)})$. Conceptually, ... more >>>

TR14-145 | 4th November 2014
Yuan Li, Alexander Razborov, Benjamin Rossman

On the $AC^0$ Complexity of Subgraph Isomorphism

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let
$Subgraph(P)$ denote the problem of deciding whether a given graph $G$
contains a subgraph isomorphic to $P$. We are interested in
$AC^0$-complexity of this problem, determined by the smallest possible exponent
$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ... more >>>

TR12-134 | 22nd October 2012
Alexander Razborov, Emanuele Viola

Real Advantage

Revisions: 1

We highlight the challenge of proving correlation bounds
between boolean functions and integer-valued polynomials,
where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12
\log_2 \log_2 n$ have zero correlation with parity. Such a
result is false for modular and threshold polynomials.
Its proof ... more >>>

TR10-198 | 13th December 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

Parameterized Bounded-Depth Frege is Not Optimal

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordström 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

TR08-081 | 11th September 2008
Alexander Razborov

A simple proof of Bazzi's theorem

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.
The aim of this note is to present a simplified version of his proof.

more >>>

TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

The Sign-Rank of AC^0

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

TR07-086 | 7th September 2007
Venkatesan Guruswami, James R. Lee, Alexander Razborov

Almost Euclidean subspaces of $\ell_1^N$ via expander codes

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X
\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and ... more >>>

TR06-050 | 18th April 2006
Alexander Razborov, Sergey Yekhanin

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

A two server private information retrieval (PIR) scheme
allows a user U to retrieve the i-th bit of an
n-bit string x replicated between two servers while each
server individually learns no information about i. The main
parameter of interest in a PIR scheme is its communication
complexity, namely the ... more >>>

TR01-075 | 2nd November 2001
Alexander Razborov

Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

We show that every resolution proof of the {\em functional} version
$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split
between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log
m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number
of pigeons $m$ is arbitrary.

more >>>

TR01-055 | 26th July 2001
Alexander Razborov

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

Recently, Raz established exponential lower bounds on the size
of resolution proofs of the weak pigeonhole principle. We give another
proof of this result which leads to better numerical bounds. Specifically,
we show that every resolution proof of $PHP^m_n$ must have size
$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an
$\exp\of{\Omega(n^{1/3})}$ bound when ... more >>>

TR00-023 | 11th May 2000
Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

Pseudorandom Generators in Propositional Proof Complexity

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em
hard} for a propositional proof system $P$ if $P$ can not efficiently
prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for
{\em any} string $b\in\{0,1\}^m$. We consider a variety of
``combinatorial'' pseudorandom generators inspired by the
Nisan-Wigderson generator on the one hand, and ... more >>>

TR99-040 | 20th October 1999
Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

Space Complexity in Propositional Calculus

We study space complexity in the framework of
propositional proofs. We consider a natural model analogous to
Turing machines with a read-only input tape, and such
popular propositional proof systems as Resolution, Polynomial
Calculus and Frege systems. We propose two different space measures,
corresponding to the maximal number of bits, ... more >>>

TR99-014 | 30th May 1999
Alexander Razborov, Nikolay Vereshchagin

One Property of Cross-Intersecting Families

Assume that A, B are finite families of n-element sets.
We prove that there is an element that simultaneously
belongs to at least |A|/2n sets
in A and to at least |B|/2n sets in B. We use this result to prove
that for any inconsistent DNF's F,G with OR ... more >>>

TR96-037 | 14th June 1996
Stasys Jukna, Alexander Razborov

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
more >>>

TR94-010 | 12th December 1994
Alexander Razborov, Steven Rudich

Natural Proofs

We introduce the notion of {\em natural} proof.
We argue that the known proofs of lower bounds on the complexity of explicit
Boolean functions in non-monotone models
fall within our definition of natural.
We show based on a hardness assumption
that natural proofs can't prove superpolynomial lower bounds ... more >>>

TR94-006 | 12th December 1994
Alexander Razborov

On provably disjoint NP-pairs

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets
representable in a theory $T$ of Bounded Arithmetic in the sense that
$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$
we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the
class of disjoint ... more >>>

ISSN 1433-8092 | Imprint