Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pavel Pudlak:

TR17-106 | 16th June 2017
Mateus de Oliveira Oliveira, Pavel Pudlak

Representations of Monotone Boolean Functions by Linear Programs

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of
computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.
2. MLP circuits are exponentially stronger than monotone span programs.
3. ... more >>>

TR17-048 | 14th March 2017
Pavel Hrubes, Pavel Pudlak

A note on monotone real circuits

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

TR17-042 | 6th March 2017
Pavel Hrubes, Pavel Pudlak

Random formulas, monotone circuits, and interpolation

We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>>

TR16-175 | 8th November 2016
Pavel Pudlak, Neil Thapen

Random resolution refutations

Revisions: 1

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the ... more >>>

TR14-138 | 29th October 2014
Nicola Galesi, Pavel Pudlak, Neil Thapen

The space complexity of cutting planes refutations

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. We show that any ... more >>>

TR14-011 | 22nd January 2014
Dmitry Gavinsky, Pavel Pudlak

Partition Expanders

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is required that the number of edges between any ... more >>>

TR13-092 | 19th June 2013
Pavel Pudlak, Arnold Beckmann, Neil Thapen

Parity Games and Propositional Proofs

Revisions: 1

A propositional proof system is \emph{weakly automatizable} if there
is a polynomial time algorithm which separates satisfiable formulas
from formulas which have a short refutation in the system, with
respect to a given length bound. We show that if the resolution
proof system is weakly automatizable, ... more >>>

TR13-038 | 13th March 2013
Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

The complexity of proving that a graph is Ramsey

Revisions: 1

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>

TR11-162 | 7th December 2011
Pavel Pudlak

A lower bound on the size of resolution proofs of the Ramsey theorem

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.

more >>>

TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

TR10-113 | 16th July 2010
Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

Pseudorandom Generators for Group Products

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

On convex complexity measures

Khrapchenko's classical lower bound $n^2$ on the formula size of the
parity function~$f$ can be interpreted as designing a suitable
measure of subrectangles of the combinatorial rectangle
$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we
arrived at the concept of \emph{convex measures}. We prove the
more >>>

TR07-074 | 7th August 2007
Dmitry Gavinsky, Pavel Pudlak

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

We give the first exponential separation between quantum and
classical multi-party
communication complexity in the (non-interactive) one-way and
simultaneous message
passing settings.
For every k, we demonstrate a relational communication problem
between k parties
that can be solved exactly by a quantum simultaneous message passing
protocol of
cost ... more >>>

TR07-032 | 27th March 2007
Pavel Pudlak

Quantum deduction rules

We define propositional quantum Frege proof systems and compare it
with classical Frege proof systems.

more >>>

TR05-122 | 31st October 2005
Pavel Pudlak

A nonlinear bound on the number of wires in bounded depth circuits

We shall prove a lower bound on the number of edges in some bounded
depth graphs. This theorem is stronger than lower bounds proved on
bounded depth superconcentrators and enables us to prove a lower bound
on certain bounded depth circuits for which we cannot use
superconcentrators: we prove that ... more >>>

TR04-004 | 13th January 2004
Ramamohan Paturi, Pavel Pudlak

Circuit lower bounds and linear codes

In 1977 Valiant proposed a graph theoretical method for proving lower
bounds on algebraic circuits with gates computing linear functions.
He used this method to reduce the problem of proving
lower bounds on circuits with linear gates to to proving lower bounds
on the rigidity of a matrix, a ... more >>>

TR02-007 | 14th January 2002
Pavel Pudlak

Monotone complexity and the rank of matrices

Comments: 1

The rank of a matrix has been used a number of times to prove lower
bounds on various types of complexity. In particular it has been used
for the size of monotone formulas and monotone span programs. In most
cases that this approach was used, there is not a single ... more >>>

TR01-044 | 14th June 2001
Pavel Pudlak

On reducibility and symmetry of disjoint NP-pairs

We consider some problems about pairs of disjoint $NP$ sets.
The theory of these sets with a natural concept of reducibility
is, on the one hand, closely related to the theory of proof
systems for propositional calculus, and, on the other, it
resembles the theory of NP completeness. Furthermore, such
more >>>

TR00-087 | 14th November 2000
Albert Atserias, Nicola Galesi, Pavel Pudlak

Monotone simulations of nonmonotone propositional proofs

We show that an LK proof of size $m$ of a monotone sequent (a sequent

that contains only formulas in the basis $\wedge,\vee$) can be turned

into a proof containing only monotone formulas of size $m^{O(\log m)}$

and with the number of proof lines polynomial in $m$. Also we show

... more >>>

TR98-042 | 27th July 1998
Pavel Pudlak

A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

Comments: 1

We consider computations of linear forms over {\bf R} by
circuits with linear gates where the absolute values
coefficients are bounded by a constant. Also we consider a
related concept of restricted rigidity of a matrix. We prove
some lower bounds on the size of such circuits and the
more >>>

TR97-043 | 25th September 1997
Bruno Codenotti, Pavel Pudlak, Giovanni Resta

Some structural properties of low rank matrices related to computational complexity

Revisions: 1 , Comments: 1

We consider the conjecture stating that a matrix with rank
$o(n)$ and ones on the main diagonal must contain nonzero
entries on a $2\times 2$ submatrix with one entry on the main
diagonal. We show that a slightly stronger conjecture implies
that ... more >>>

TR97-042 | 22nd September 1997
Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

Razborov~\cite{Razborov96} recently proved that polynomial
calculus proofs of the pigeonhole principle $PHP_n^m$ must have
degree at least $\ceiling{n/2}+1$ over any field. We present a
simplified proof of the same result. The main
idea of our proof is the same as in the original proof
of Razborov: we want to describe ... more >>>

TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

We prove an unexpected upper bound on a communication game proposed
by Jeff Edmonds and Russell Impagliazzo as an approach for
proving lower bounds for time-space tradeoffs for branching programs.
Our result is based on a generalization of a construction of Erdos,
Frankl and Rodl of a large 3-hypergraph ... more >>>

TR94-023 | 12th December 1994
Matthias Krause, Pavel Pudlak

On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

We investigate the computational power of depth two circuits
consisting of $MOD^r$--gates at the bottom and a threshold gate at
the top (for short, threshold--$MOD^r$ circuits) and circuits with
two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we
will show the following results

(i) For all prime numbers ... more >>>

TR94-018 | 12th December 1994
Jan Krajicek, Pavel Pudlak, Alan Woods

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$
$\epsilon_d>0,$ on the length of proofs of an explicit sequence of
tautologies, based on the Pigeonhole Principle, in proof systems
using formulas of depth $d,$ for any constant $d.$ This is the
largest lower bound for the strongest proof system, for which ... more >>>

TR94-013 | 12th December 1994
Pavel Pudlak

Complexity Theory and Genetics

We introduce a population genetics model in which the operators
are effectively computable -- computable in polynomial time on
Probabilistic Turing Machines. We shall show that in this model
a population can encode easily large amount of information
from enviroment into genetic code. Then it can process the
information as ... more >>>

ISSN 1433-8092 | Imprint