Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
1
vote
0answers
112 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 ...
4
votes
0answers
80 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 ...
7
votes
2answers
315 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 ...
2
votes
0answers
113 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
213 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 ...
3
votes
1answer
148 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 ...
5
votes
0answers
89 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
325 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
155 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 ...
9
votes
2answers
315 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
248 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 ...
7
votes
1answer
130 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 ...
18
votes
2answers
524 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 ...
14
votes
1answer
259 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
107 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
382 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 ...
23
votes
3answers
539 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 ...
4
votes
0answers
89 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
95 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 ...
10
votes
1answer
178 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 ...
17
votes
2answers
492 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
463 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
221 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
118 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 ...
9
votes
2answers
169 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 ...
14
votes
1answer
365 views
Can we count in depth $\frac{\lg n}{\lg \lg n}$?
Can we compute an n-bit threshold gate by polynomial size circuits of depth $\frac{\lg n}{\lg \lg n}$ (unbounded fan-in)? Alternatively, can we count the number of 1s in the input bits using these ...
32
votes
0answers
513 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 ...
16
votes
2answers
277 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
92 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 ...
7
votes
0answers
189 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.
...
25
votes
3answers
835 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 ...
13
votes
1answer
278 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 ...
17
votes
1answer
664 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 ...
11
votes
1answer
205 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 ...
8
votes
1answer
162 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 ...
0
votes
0answers
66 views
What is the best known hardness result for Factoring? [duplicate]
Possible Duplicate:
Are the problems PRIMES, FACTORING known to be P-hard?
In particular, do we know that $\mathrm{Factoring}$ is hard for $\mathsf{AC^0[p]}$, $\mathsf{ACC}$, or ...
19
votes
2answers
502 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 ...
17
votes
0answers
335 views
Approximate degree of $\textrm{AC}^0$
EDIT (v2): Added a section at the end on what I know about the problem.
Question
This question is mainly a reference request. I don't know much about the problem. I want to know if there has been ...
10
votes
1answer
177 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 ...
-1
votes
1answer
208 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 ...
5
votes
1answer
306 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 ...
3
votes
2answers
310 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 ...
6
votes
1answer
113 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
131 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 ...
4
votes
1answer
117 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
238 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 ...
19
votes
3answers
588 views
Clique problem on fixed graphs
As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this ...
21
votes
2answers
634 views
Are AND&OR circuits P-complete?
The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? ...
2
votes
1answer
229 views
Questions about computing matrix rigidity
Matrix rigidity was introduced by Valiant in 1977:
The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the
smallest number of entries of $M$ that must be changed in order to
reduce ...
6
votes
2answers
384 views
(0,1)-vector XOR problem
this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. ...
