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.

9
votes
0answers
151 views

$\mathsf{TC^0}$-completeness and reductions

AFAIU, we don't know any problem which is complete for $\mathsf{TC^0}$ w.r.t. many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$). On the other hand, proving that they don't exist would ...
12
votes
2answers
455 views

Does the $\mathsf{TC^0}$ hierarchy collapse?

Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)? The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between ...
3
votes
0answers
171 views

Natural Proofs and methods for polylog depth circuit lower bounds

I have a question about the following question and its answer. Status on circuit lower bounds for polylog-bounded depth circuits In the above question, it is asked about methods to prove lower ...
13
votes
1answer
197 views

What is the minimum required depth of reductions for NP-hardness of SAT?

As everyone knows, SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions. It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions. My questions is what is the minimum ...
11
votes
0answers
500 views

Has there been any result which does not have any Natural Proofs?

Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994). Has there ...
2
votes
0answers
160 views

Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature

Consider the following building blocks, which can be used to construct a logic circuit: basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$. generators of ...
6
votes
1answer
188 views

Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits

Beigel and Tarui's transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the ...
9
votes
2answers
605 views

Cancellation and determinant

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
6
votes
0answers
769 views

k-CNF ←→ k-DNF conversion to minimize errors

the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
7
votes
2answers
257 views

How efficiently can circuits over sets of naturals be transformed to boolean circuits?

I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this ...
6
votes
1answer
572 views

How powerful are nondeterministic constant-depth circuits?

A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}...
5
votes
0answers
138 views

Multiple output $AC^0$ circuits?

A naive question perhaps: are there any results/references about $AC^0$ circuits with multiple outputs? Namely, I'm interested in the natural generalization of the Min-$AC^0_d$ problem (find a circuit ...
11
votes
2answers
513 views

On fooling $AC^0$

I have a few questions regarding fooling constant depth circuits. It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the ...
2
votes
2answers
852 views

Quantum oracle implementation overhead

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...
17
votes
2answers
731 views

Status on circuit lower bounds for polylog-bounded depth circuits

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
8
votes
1answer
360 views

logic in the presence of doubt, uncertainty, lies

I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity. This is not a gratuitous exercise. This may have applications to computer ...
8
votes
1answer
173 views

Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]?

Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:10.1145/276698.276872) on the exponential lower bounds for Depth 3 arithmetic circuits computing $\...
22
votes
2answers
1k views

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
19
votes
2answers
443 views

Relation between $AC^0$ and regular languages

Let $\mathsf{REG}$ be the class of all regular languages. It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for ...
5
votes
1answer
273 views

Monotonicity and Threshold function

I have a question about a answer of a question which is proposed in this stack exchange. The Past Question One of the most basic result in circuit complexity is the constnat depth cirdcuit lower ...
10
votes
1answer
1k views

How many disjoint edge-cuts a DAG must have?

The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that ...
25
votes
3answers
820 views

Constructivity in Natural Proof and Geometric Complexity

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$. Constructivity in Natural ...
5
votes
0answers
187 views

Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
8
votes
0answers
120 views

Can polynomial-sized circuits use garbage?

This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if $(x,r(x))\...
10
votes
1answer
339 views

Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds

My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$? What is wrong ...
20
votes
2answers
596 views

Bounded depth probability distributions

Two related questions about bounded depth computing: 1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
6
votes
2answers
2k views

Complexity of the halting problem

One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind: $...
8
votes
1answer
334 views

Complexity of sorting

It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$. If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the ...
3
votes
1answer
323 views

Constant Depth Circuit Computing Threshold Function

One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma. Another popular function MAJORITY has also lower ...
11
votes
2answers
312 views

Hierarchy theorems for circuit depth

What kind of hierarchy theorems are there for circuit depth? Statements like if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(...
19
votes
1answer
658 views

Can we count in depth $\frac{\lg n}{\lg \lg n}$?

Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these ...
45
votes
0answers
1k views

Monotone complexity of s-t connectivity

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs $...
18
votes
2answers
827 views

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
-1
votes
1answer
108 views

Weights in threshold circuits

I have the following questions about the weights used in threshold circuits: What is the difference beween real weight and non-negative real one? Integer weights can efficiently simulate real ...
13
votes
1answer
457 views

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability. ...
27
votes
3answers
952 views

A Notion of Monotone Quantum Circuits

In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the ...
15
votes
1answer
393 views

Characterization of read-once formulae over the full binary basis

Background A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (...
21
votes
2answers
985 views

Can addition be carried out in less than depth 5?

Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
13
votes
2answers
389 views

Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma. Can we develop a Switching Lemma result to prove a size lower-bound ...
9
votes
1answer
283 views

FO-uniform AC0 with some predicate

My question is about finite model theory/descriptive complexity, so $FO(R)$ will mean "first order over finite binary words, using predicates Rs and a unary predicate P true on the position of the 1 ...
21
votes
2answers
760 views

Circuit lower bounds and kolmogorov complexity

Consider the following reasoning: Let $K(x)$ denote the Kolmogorov complexity of the string $x$. Chaitin's incompleteness theorem says that for any consistent and sufficiently strong formal ...
24
votes
1answer
692 views

Approximate degree of $\textrm{AC}^0$

EDIT (v2): Added a section at the end on what I know about the problem. EDIT (v3): Added discussion on threshold degree at the end. Question This question is mainly a reference request. I don't ...
11
votes
1answer
312 views

Ruzzo-Simon-Tompa oracle access mechanism

In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some more pathological examples in this vein in ...
0
votes
1answer
339 views

Proof Complexity and Circuit Lower bound for coNP

I have two questions (1)Circuit lower bound for coNP TAUT is a set of formulae such that any formula in TAUT is satisfied for all boolean assignments. UnSAT is the complement problem of SAT. It is ...
7
votes
1answer
497 views

Razborov's Approximation methods

The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem. People in parameterized complexity theory strongly believe that k-...
3
votes
2answers
456 views

Boolean Circuit in a Black Box?

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here. Let's equip a normal Turing machine with a "black box ...
7
votes
1answer
232 views

Non-uniform hierarchy theorem for approximating functions

It is easy to show (by probabilistic argument) that there exist functions that require circuits of size $O(2^n/n)$. This, in turn, can be used to prove a non-deterministic hierarchy theorem showing (...
4
votes
1answer
180 views

Computing every boolean function with a polynomial over $\mathbb{F}_3$?

The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\...
5
votes
1answer
195 views

Other types of uniformity for circuits (incl. by small modifications)

I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ ...
11
votes
2answers
310 views

Variants of direct product theorems

A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once. Typical direct product theorems (e.g., Yao's XOR Lemma) look at average-...