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

TR23-001 | 5th January 2023
Prerona Chatterjee, Pavel Hrubes

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>> TR20-189 | 24th December 2020 Pavel Hrubes, Amir Yehudayoff #### Shadows of Newton polytopes 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 #### On$\epsilon$-sensitive monotone computations 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

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