  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > AUTHORS > PAVEL HRUBES:
All reports by Author Pavel Hrubes:

TR20-189 | 24th December 2020
Pavel Hrubes, Amir Yehudayoff

We define the shadow complexity of a polytope P as the maximum number of vertices in a linear projection of $P$ to the plane. We describe connections to algebraic complexity and to parametrized optimization. We also provide several basic examples and constructions, and develop tools for bounding shadow complexity.

more >>>

TR19-036 | 5th March 2019
Pavel Hrubes

#### On the complexity of computing a random Boolean function over the reals

Revisions: 1

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:

(i) every $f$ can be defined by a formula of size $O(n)$,
(ii) if $A$ is required to have at most $k\geq 1$ ... more >>>

TR19-034 | 5th March 2019
Pavel Hrubes

Revisions: 1

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>> TR19-026 | 28th February 2019 Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff #### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits Revisions: 1 There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets$S_1,\ldots,S_k \subset [n]$is balancing if for every subset$X \subset \{1,2,\ldots,n\}$of size$n/2$, there is an$i \in [k]$so that$|S_i \cap X| = ... 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 >>>

TR15-164 | 13th October 2015
Pavel Hrubes, Amir Yehudayoff

#### On isoperimetric profiles and computational complexity

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

TR15-067 | 21st April 2015
Pavel Hrubes

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

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

TR14-020 | 18th February 2014
Pavel Hrubes, Anup Rao

#### Circuits with Medium Fan-In

Revisions: 1

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

TR13-128 | 16th September 2013
Pavel Hrubes

#### A note on semantic cutting planes

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

TR12-121 | 25th September 2012
Pavel Hrubes

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

Revisions: 2

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

TR12-061 | 16th May 2012
Pavel Hrubes, Amir Yehudayoff

#### Formulas are exponentially stronger than monotone circuits in non-commutative setting

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

TR11-174 | 30th December 2011
Pavel Hrubes, Iddo Tzameret

#### Short Proofs for the Determinant Identities

Revisions: 1

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

TR11-088 | 7th June 2011
Pavel Hrubes

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

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

TR10-040 | 10th March 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

#### Relationless completeness and separations

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.
We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ... more >>>

TR10-021 | 21st February 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

#### Non-commutative circuits and the sum-of-squares problem

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... 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 >>>

ISSN 1433-8092 | Imprint