Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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 >>>

TR19-018 | 18th February 2019
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

AC0[p] Lower Bounds against MCSP via the Coin Problem

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

TR19-021 | 19th February 2019
Rahul Ilango

$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>

ISSN 1433-8092 | Imprint