  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > KEYWORD > BOUNDED ARITHMETIC:
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 >>>

TR23-008 | 2nd February 2023
Ond?ej Ježil

#### Limits of structures and Total NP Search Problems

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables . We prove ... more >>>

TR23-022 | 11th March 2023
Jiatu Li, Igor Carboni Oliveira

#### Unprovability of strong complexity lower bounds in bounded arithmetic

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory $\textbf{APC}_1$ (2007) and of higher levels of Buss's hierarchy $\textbf{S}^i_2$ (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory ... more >>>

TR23-038 | 28th March 2023
Rahul Ilango, Jiatu Li, Ryan Williams

#### Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

ISSN 1433-8092 | Imprint