Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [circuit-complexity]

Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.

40
votes
3answers
2k views

Circuit lower bounds over arbitrary sets of gates

In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis ...
21
votes
6answers
1k views

References on Circuit Lower Bounds

Preamble Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than ...
21
votes
6answers
966 views

What is the best way to get a close-to-fair coin toss from identical biased coins?

(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many ...
2
votes
1answer
274 views

Complexity of advice language?

Let $L$ be a language in P/poly. There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$. Consider the language $A(M)$ of all advice strings ...
16
votes
5answers
360 views

Stronger notions of uniformizations?

One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing ...
14
votes
1answer
277 views

Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It ...
8
votes
1answer
225 views

Circuit complexity and statistical tests

A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with ...
15
votes
2answers
889 views

Barriers and Monotone Circuit Complexity

Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit ...
20
votes
2answers
803 views

Problems between NC and P: How many have been resolved from this list?

In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (...
4
votes
1answer
285 views

On Defining Probabilistic/Nondeterministic Circuits

Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit. The standard way of defining probabilistic/nondeterministic circuits ...
11
votes
1answer
398 views

Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...
16
votes
3answers
725 views

Which $AC^0$ problems are not “truly feasible”?

Neil Immerman's famous Picture of The World is the following (click to enlarge):                    &...
21
votes
2answers
503 views

Lower bounds for constant-depth formulae?

We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known ...