Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with TC^0:
TR96-023 | 21st March 1996
Eric Allender

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ... more >>>

TR05-149 | 7th December 2005
Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Grid Graph Reachability Problems

Revisions: 1

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since
* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and
* reachability on certain classes of grid graphs gives ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

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

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

TR21-002 | 8th January 2021
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Fooling Constant-Depth Threshold Circuits

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>

ISSN 1433-8092 | Imprint