Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Uniformity:
TR98-020 | 10th April 1998
Andris Ambainis, David Mix Barrington, Huong LeThanh

On Counting $AC^0$ Circuits with Negative Constants

Continuing the study of the relationship between $TC^0$,
$AC^0$ and arithmetic circuits, started by Agrawal et al.
(IEEE Conference on Computational Complexity'97),
we answer a few questions left open in this
paper. Our main result is that the classes Diff$AC^0$ and
Gap$AC^0$ ... more >>>

TR00-065 | 7th September 2000
Eric Allender, David Mix Barrington

Uniform Circuits for Division: Consequences and Problems

Comments: 2

The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which ... more >>>

TR01-033 | 27th April 2001
Eric Allender, David Mix Barrington, William Hesse

Uniform Circuits for Division: Consequences and Problems

Integer division has been known to lie in P-uniform TC^0 since
the mid-1980's, and recently this was improved to DLOG-uniform
TC^0. At the time that the results in this paper were proved and
submitted for conference presentation, it was unknown whether division
lay in DLOGTIME-uniform TC^0 (also known as ... more >>>

TR11-095 | 22nd June 2011
Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

Low uniform versions of NC1

Revisions: 1

In the setting known as DLOGTIME-uniformity,
the fundamental complexity classes
$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several
robust characterizations.
In this paper we refine uniformity further and examine the impact
of these refinements on $NC^1$ and its subclasses.
When applied to the logarithmic circuit depth characterization of $NC^1$,
some refinements leave ... more >>>

TR14-037 | 21st March 2014
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Succinct and explicit circuits for sorting and connectivity

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

ISSN 1433-8092 | Imprint