Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-132 | 22nd March 2024 15:51

New lower bounds for Polynomial Calculus over non-Boolean bases

RSS-Feed




Revision #1
Authors: Yogesh Dahiya, Meena Mahajan, Sasank Mouli
Accepted on: 22nd March 2024 15:51
Downloads: 54
Keywords: 


Abstract:

In this paper, we obtain new size lower bounds for proofs in the
Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed
to $0,1$): We establish a lifting theorem using an asymmetric gadget
$G$, showing that for an unsatisfiable formula $F$, the lifted
formula $F \circ G$ requires PC size $2^{\Omega(d)}$, where $d$ is
the degree required to refute $F$. Our lower bound does not depend
on the number of variables $n$, and holds over every field. The
only previously known size lower bounds in this setting were
established quite recently in [Sokolov, STOC 2020] using lifting
with another (symmetric) gadget. The size lower bound there is
$2^{\Omega((d-d_0)^2/n)}$ (where $d_0$ is the degree of the initial
equations arising from the formula), and is shown to hold only over
the reals.

2. When the PC refutation proceeds over a finite field
$\mathbb{F}_p$ and is allowed to use extension variables: We show
that there is an unsatisfiable formula with $N$ variables for which
any PC refutation using $N^{1+\epsilon(1-\delta)}$ extension
variables, each of arity at most $N^{1-\epsilon}$ and size at most
$N^c$, must have size $\exp(\Omega(N^{\epsilon\delta}/\poly\log
N))$. Our proof achieves these bounds by an XOR-ification of the
generalised PHP$^{m,r}_n$ formulas from [Razborov, CC 1998].

The only previously known lower bounds for PC in this setting are
those obtained in [ImpagliazzoMouliPitassi, CCC 2023]; in those
bounds the number of extension variables is required to be
sub-quadratic, and their arity is restricted to logarithmic in
the number of original variables. Our result generalises these,
and demonstrates a tradeoff between the number and the arity of
extension variables.


Paper:

TR23-132 | 12th September 2023 06:39

New lower bounds for Polynomial Calculus over non-Boolean bases





TR23-132
Authors: Yogesh Dahiya, Meena Mahajan, Sasank Mouli
Publication: 12th September 2023 07:27
Downloads: 301
Keywords: 


Abstract:


In this paper, we obtain new size lower bounds for proofs in the
Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed
to $0,1$): We establish a lifting theorem using an asymmetric gadget
$G$, showing that for an unsatisfiable formula $F$, the lifted
formula $F \circ G$ requires PC size $2^{\Omega(d)}$, where $d$ is
the degree required to refute $F$. Our lower bound does not depend
on the number of variables $n$, and holds over every field. The
only previously known size lower bounds in this setting were
established quite recently in [Sokolov, STOC 2020] using lifting
with another (symmetric) gadget. The size lower bound there is
$2^{\Omega((d-d_0)^2/n)}$ (where $d_0$ is the degree of the initial
equations arising from the formula), and is shown to hold only over
the reals.

2. When the PC refutation proceeds over a finite field
$\mathbb{F}_p$ and is allowed to use extension variables: We show
that there is an unsatisfiable formula with $N$ variables for which
any PC refutation using $N^{1+\epsilon(1-\delta)}$ extension
variables, each of arity at most $N^{1-\epsilon}$ and size at most
$N^c$, must have size $\exp(\Omega(N^{\epsilon\delta}/\poly\log
N))$. Our proof achieves these bounds by an XOR-ification of the
generalised PHP$^{m,r}_n$ formulas from [Razborov, CC 1998].

The only previously known lower bounds for PC in this setting are
those obtained in [ImpagliazzoMouliPitassi, CCC 2023]; in those
bounds the number of extension variables is required to be
sub-quadratic, and their arity is restricted to logarithmic in
the number of original variables. Our result generalises these,
and demonstrates a tradeoff between the number and the arity of
extension variables.



ISSN 1433-8092 | Imprint