Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ACC^0:
Reports tagged with ACC^0:
TR04-108 | 24th November 2004
Eric Allender, Samir Datta, Sambuddha Roy

Topology inside NC^1

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.
We consider other generalizations 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 >>>


TR18-076 | 22nd April 2018
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 2

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>


TR19-031 | 4th March 2019
Lijie Chen

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ... more >>>




ISSN 1433-8092 | Imprint