Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with bounded arithmetic:
TR01-024 | 1st March 2001
Stephen Cook, Antonina Kolokolova

A second-order system for polynomial-time reasoning based on Graedel's theorem

We introduce a second-order system V_1-Horn of bounded arithmetic
formalizing polynomial-time reasoning, based on Graedel's
second-order Horn characterization of P. Our system has
comprehension over P predicates (defined by Graedel's second-order
Horn formulas), and only finitely many function symbols. Other
systems of polynomial-time reasoning either ... more >>>

TR02-051 | 16th July 2002
Chris Pollett

Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

The use of Nepomnjascij's Theorem in the proofs of independence results
for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ... more >>>

TR03-055 | 20th July 2003
Jan Krajicek

Implicit proofs

We describe a general method how to construct from
a propositional proof system P a possibly much stronger
proof system iP. The system iP operates with
exponentially long P-proofs described ``implicitly''
by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF,
corresponds to bounded ... more >>>

TR05-017 | 28th January 2005
Phong Nguyen

Two-Sorted Theories for L, SL, NL and P

We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP
that characterize the classes L, SL, NL and P in the same
way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy.
Our theories arise from natural combinatorial problems, namely the st-Connectivity
Problem and the Circuit Value Problem.
It ... more >>>

TR13-077 | 14th May 2013
Ján Pich

Circuit Lower Bounds in Bounded Arithmetics

We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas ... more >>>

TR13-116 | 29th August 2013
Albert Atserias, Moritz Müller, Sergi Oliva

Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

The relativized weak pigeonhole principle states that if at least $2n$ out of $n^2$ pigeons fly into $n$ holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{(\log n)^{3/2-\epsilon}}$ for every $\epsilon > 0$ and every sufficiently ... more >>>

TR13-149 | 28th October 2013
Albert Atserias, Neil Thapen

The Ordering Principle in a Fragment of Approximate Counting

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

TR16-071 | 1st May 2016
Jan Krajicek, Igor Carboni Oliveira

Unprovability of circuit upper bounds in Cook's theory PV

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>

TR17-144 | 27th September 2017
Moritz Müller, Ján Pich

Feasibly constructive proofs of succinct weak circuit lower bounds

Revisions: 1

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

TR18-184 | 5th November 2018
Iddo Tzameret, Stephen Cook

Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

TR21-095 | 8th July 2021
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the ... more >>>

TR22-023 | 19th February 2022
Erfan Khaniki

Nisan--Wigderson generators in Proof Complexity: New lower bounds

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

TR22-025 | 15th February 2022
Oliver Korten

Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of ``incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the ``compression problem,'' where we are given ... more >>>

ISSN 1433-8092 | Imprint