Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AC0[P]:
Reports tagged with AC0[p]:
TR16-008 | 26th January 2016
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

#### Algorithms from Natural Lower Bounds

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

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

#### Feasibly constructive proofs of succinct weak circuit lower bounds

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-004 | 3rd January 2018
Aayush Ojha, Raghunath Tewari

#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

Recently, perfect matching in bounded planar cutwidth bipartite graphs
$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that
the problem is in AC$^0$.
In this paper, we disprove their conjecture by showing that the problem is
not in AC$^0[p^{\alpha}]$ for every prime $p$. ... more >>>

ISSN 1433-8092 | Imprint