All reports by Author Pavel Hrubes:

__
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

__
TR15-164
| 13th October 2015
__

Pavel Hrubes, Amir Yehudayoff#### On isoperimetric profiles and computational complexity

__
TR15-067
| 21st April 2015
__

Pavel Hrubes#### On hardness of multilinearization, and VNP completeness in characteristics two

__
TR14-020
| 18th February 2014
__

Pavel Hrubes, Anup Rao#### Circuits with Medium Fan-In

Revisions: 1

__
TR13-128
| 16th September 2013
__

Pavel Hrubes#### A note on semantic cutting planes

__
TR12-121
| 25th September 2012
__

Pavel Hrubes#### A note on the real $\tau$-conjecture and the distribution of roots

Revisions: 2

__
TR12-061
| 16th May 2012
__

Pavel Hrubes, Amir Yehudayoff#### Formulas are exponentially stronger than monotone circuits in non-commutative setting

__
TR11-174
| 30th December 2011
__

Pavel Hrubes, Iddo Tzameret#### Short Proofs for the Determinant Identities

Revisions: 1

__
TR11-088
| 7th June 2011
__

Pavel Hrubes#### How much commutativity is needed to prove polynomial identities?

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 Hrubes, Amir Yehudayoff

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

Pavel Hrubes

For a boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$, let $\hat{f}$ be the unique multilinear polynomial such that $f(x)=\hat{f}(x)$ holds for every $x\in \{0,1\}^n$. We show that, assuming $\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable $f$ such that $\hat{f}$ requires super-polynomial arithmetic circuits. In fact, this $f$ can be taken as a monotone 2-CNF, ... more >>>

Pavel Hrubes, Anup Rao

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth ... more >>>

Pavel Hrubes

We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>>

Pavel Hrubes

Koiran's real $\tau$-conjecture asserts that if a non-zero real polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij},$

where each $f_{ij}$ contains at most $k$ monomials, then the number of distinct real roots of $f$ is polynomial in $pqk$. We show that the conjecture implies quite a strong property of the ...
more >>>

Pavel Hrubes, Amir Yehudayoff

We give an example of a non-commutative monotone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general ... more >>>

Pavel Hrubes, Iddo Tzameret

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>

Pavel Hrubes

Let $f$ be a non-commutative polynomial such that $f=0$ if we assume that the variables in $f$ commute. Let $Q(f)$ be the smallest $k$ such that there exist polynomials $g_1,g_1', g_2, g_2',\dots, g_k, g_k' $ with \[f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,\]

where $[g,h]=gh-hg$. Then $Q(f)\leq {n\choose 2}$, where ...
more >>>