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

__
TR17-048
| 14th March 2017
__

Pavel Hrubes, Pavel Pudlak#### A note on monotone real circuits

__
TR17-042
| 6th March 2017
__

Pavel Hrubes, Pavel Pudlak#### Random formulas, monotone circuits, and interpolation

__
TR16-175
| 8th November 2016
__

Pavel Pudlak, Neil Thapen#### Random resolution refutations

Revisions: 1

__
TR14-138
| 29th October 2014
__

Nicola Galesi, Pavel Pudlak, Neil Thapen#### The space complexity of cutting planes refutations

__
TR14-011
| 22nd January 2014
__

Dmitry Gavinsky, Pavel Pudlak#### Partition Expanders

__
TR13-092
| 19th June 2013
__

Pavel Pudlak, Arnold Beckmann, Neil Thapen#### Parity Games and Propositional Proofs

Revisions: 1

__
TR13-038
| 13th March 2013
__

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen#### The complexity of proving that a graph is Ramsey

Revisions: 1

__
TR11-162
| 7th December 2011
__

Pavel Pudlak#### A lower bound on the size of resolution proofs of the Ramsey theorem

__
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

__
TR10-113
| 16th July 2010
__

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak#### Pseudorandom Generators for Group Products

__
TR09-040
| 20th April 2009
__

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak#### On convex complexity measures

__
TR07-074
| 7th August 2007
__

Dmitry Gavinsky, Pavel Pudlak#### Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

__
TR07-032
| 27th March 2007
__

Pavel Pudlak#### Quantum deduction rules

__
TR05-122
| 31st October 2005
__

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

__
TR04-004
| 13th January 2004
__

Ramamohan Paturi, Pavel Pudlak#### Circuit lower bounds and linear codes

__
TR02-007
| 14th January 2002
__

Pavel Pudlak#### Monotone complexity and the rank of matrices

Comments: 1

__
TR01-044
| 14th June 2001
__

Pavel Pudlak#### On reducibility and symmetry of disjoint NP-pairs

__
TR00-087
| 14th November 2000
__

Albert Atserias, Nicola Galesi, Pavel Pudlak#### Monotone simulations of nonmonotone propositional proofs

__
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

__
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

__
TR97-042
| 22nd September 1997
__

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall#### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

__
TR95-010
| 16th February 1995
__

Pavel Pudlak, Jiri Sgall#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

__
TR94-023
| 12th December 1994
__

Matthias Krause, Pavel Pudlak#### On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

__
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

__
TR94-013
| 12th December 1994
__

Pavel Pudlak#### Complexity Theory and Genetics

Mateus de Oliveira Oliveira, Pavel Pudlak

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

Pavel Hrubes, Pavel Pudlak

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

Pavel Hrubes, Pavel Pudlak

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

Pavel Pudlak, Neil Thapen

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

Nicola Galesi, Pavel Pudlak, Neil Thapen

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

Dmitry Gavinsky, Pavel Pudlak

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

Pavel Pudlak, Arnold Beckmann, Neil Thapen

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

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

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

Pavel Pudlak

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

more >>>Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

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

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

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

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

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

Dmitry Gavinsky, Pavel Pudlak

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

Pavel Pudlak

We define propositional quantum Frege proof systems and compare it

with classical Frege proof systems.

Pavel Pudlak

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

Ramamohan Paturi, Pavel Pudlak

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

Pavel Pudlak

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

Pavel Pudlak

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

Albert Atserias, Nicola Galesi, Pavel Pudlak

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

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

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

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

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

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

Pavel Pudlak, Jiri Sgall

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

Matthias Krause, Pavel Pudlak

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

Jan Krajicek, Pavel Pudlak, Alan Woods

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

Pavel Pudlak

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