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

__
TR16-184
| 16th November 2016
__

Alexander Razborov#### On Space and Depth in Resolution

__
TR16-010
| 28th January 2016
__

Alexander Razborov#### On the Width of Semi-Algebraic Proofs and Algorithms

__
TR15-033
| 6th March 2015
__

Alexander Razborov#### An Ultimate Trade-Off in Propositional Proof Complexity

Revisions: 1

__
TR14-145
| 4th November 2014
__

Yuan Li, Alexander Razborov, Benjamin Rossman#### On the $AC^0$ Complexity of Subgraph Isomorphism

__
TR12-134
| 22nd October 2012
__

Alexander Razborov, Emanuele Viola#### Real Advantage

Revisions: 1

__
TR10-198
| 13th December 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov#### Parameterized Bounded-Depth Frege is Not Optimal

__
TR09-100
| 16th October 2009
__

Jakob NordstrÃ¶m, Alexander Razborov#### On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

__
TR08-081
| 11th September 2008
__

Alexander Razborov#### A simple proof of Bazzi's theorem

__
TR08-016
| 26th February 2008
__

Alexander Razborov, Alexander A. Sherstov#### The Sign-Rank of AC^0

__
TR07-086
| 7th September 2007
__

Venkatesan Guruswami, James R. Lee, Alexander Razborov#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

__
TR06-050
| 18th April 2006
__

Alexander Razborov, Sergey Yekhanin#### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

__
TR01-075
| 2nd November 2001
__

Alexander Razborov#### Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

__
TR01-055
| 26th July 2001
__

Alexander Razborov#### Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

__
TR00-023
| 11th May 2000
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Pseudorandom Generators in Propositional Proof Complexity

__
TR99-040
| 20th October 1999
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Space Complexity in Propositional Calculus

__
TR99-014
| 30th May 1999
__

Alexander Razborov, Nikolay Vereshchagin#### One Property of Cross-Intersecting Families

__
TR96-037
| 14th June 1996
__

Stasys Jukna, Alexander Razborov#### Neither Reading Few Bits Twice nor Reading Illegally Helps Much

__
TR94-010
| 12th December 1994
__

Alexander Razborov, Steven Rudich#### Natural Proofs

__
TR94-006
| 12th December 1994
__

Alexander Razborov#### On provably disjoint NP-pairs

Theodoros Papamakarios, Alexander Razborov

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

Alexander Razborov

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

Alexander Razborov

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

Alexander Razborov

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

Yuan Li, Alexander Razborov, Benjamin Rossman

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

Alexander Razborov, Emanuele Viola

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

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

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

Jakob NordstrÃ¶m, Alexander Razborov

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

Alexander Razborov

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.

Alexander Razborov, Alexander A. Sherstov

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

Venkatesan Guruswami, James R. Lee, Alexander Razborov

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

Alexander Razborov, Sergey Yekhanin

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

Alexander Razborov

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.

Alexander Razborov

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

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

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

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

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

Alexander Razborov, Nikolay Vereshchagin

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

Stasys Jukna, Alexander Razborov

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

Alexander Razborov, Steven Rudich

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

Alexander Razborov

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