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

learn more… | top users | synonyms

10
votes
0answers
122 views

Approximating $\textrm{AC}^{0}$ by sparse polynomials

Let $f$ be a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}$. We say that $f$ is randomly approximated with error probability $\epsilon$ by a family of polynomials $P$ if \begin{equation} \forall ...
19
votes
1answer
474 views

Kolmogorov's conjecture that $P$ has linear-size circuits

In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
4
votes
0answers
96 views

A possible application of TCS to EE: disruption-resistant circuits

Consider the following problem. We're given a circuit $C$ with $n$ binary inputs and $n$ binary outputs, computing some boolean function $f_C : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$. We assume ...
2
votes
1answer
116 views

A curious Wilf equivalence class of function compositions

I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero: 1, 1, 6, 87, 2200, 84245. ...
7
votes
1answer
251 views

Lower bounds on monotone space complexity

The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by ...
3
votes
1answer
762 views

Terminology for f(g(x)) = g(f(x))

There is a paper by Ritt from 1923 that calls the relation, $f(g(x)) = g(f(x))$, permutable functions. Is there a more recent terminology used in the literature, or is this still the standard?
6
votes
1answer
95 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
9
votes
1answer
144 views

Program Minimization

Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs? In particular my question is - Do there exist algorithms to minimize the ...
4
votes
0answers
89 views

Low space computation and branching program

One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$. I ...
10
votes
1answer
244 views

Better lower bounds than 3n for non-boolean functions?

Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related ...
5
votes
2answers
210 views

Circuit complexity of Majority function

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
-3
votes
1answer
120 views

“tree-like” vs “DAG-like” resolution

hi all there seems to be a deep/not-much-explored phenomenon in the way that SAT resolution proofs can define a tree and/or a DAG & its relationship to lower bounds/circuit complexity. could there ...
8
votes
0answers
78 views

Depth of bounded fan-in circuits for unbounded fan-in circuits

Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$. What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size ...
9
votes
0answers
303 views

Fundamental assumptions in complexity analysis

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as ...
3
votes
0answers
131 views

sketch of Razborovs paper “on the method of approximations”

(the following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
4
votes
0answers
88 views

Boolean Functions Where Sensitivity Equals Block Sensitivity

Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ ...
9
votes
2answers
183 views

Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = ...
5
votes
0answers
146 views

Complexity of Polynomial Division

Let $P(x)$ be a univariate polynomial with integer coefficients where both coefficients and degrees are in binary and let $q(x)$ be another polynomial also with integer coefficients where the degrees ...
11
votes
1answer
207 views

$\mathsf{NC^1}$ circuit evaluation

Is it known if $\mathsf{NC^1}$ circuit evaluation problem is in $\mathsf{NC^1}$? How about $\mathsf{ALogTime}$ (uniform $\mathsf{NC^1}$)? We know that circuits of depth $k$ can be evaluated ...
9
votes
2answers
178 views

Smallest Boolean circuit to generate a language

Consider a non-empty language $L$ of binary strings of length $n$. I can describe $L$ with a Boolean circuit $C$ with $n$ inputs and one output such that $C(w)$ is true iff $w \in L$: this is ...
12
votes
0answers
299 views

Williams' Method, Natural Proofs and Constructivity

I have some questions on the previous question which is written bellow. Natural Proof and Constructivity : The topic of the previous question Recently, Ryan Williams proved that Constructivity in ...
11
votes
1answer
393 views

Impagliazzo and Wigderson's famous P=BPP paper

I'm reading Impagliazzo and Wigderson's famous $\mathsf P=\mathsf{BPP}$ paper in 1997. Since I'm new to this field and the paper is a concise conference version, I have difficulty following their ...
12
votes
0answers
198 views

Are there other proofs for Barrington's theorem?

I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach? In case someone would not know the theorem: ...
2
votes
1answer
158 views

What functions can read-once branching programs compute?

Barrington's Theorem gives us that polynomial size and bounded width Branching programs can compute exactly functions in $NC_1$, are there any results known about read-once BPs - bounded width and ...
2
votes
2answers
258 views

Are Boolean circuits 'universal'

I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me. I would like to know if ...
12
votes
1answer
360 views

Hardness of noisy Boolean functions

Let $f$ be a Boolean function of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability ...
5
votes
2answers
201 views

Size hierachy for uniform circuits

There is the size hierarchy theorem for non-uniform circuits. Do we have any size hierarchy theorem for any kind of uniform circuits ? (By uniform here, I mean DLOGTIME uniform. But I don't know ...
12
votes
1answer
242 views

Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a ...
6
votes
0answers
153 views

The size of output in circuit complexity

In circuit complexity we have one circuit for each input size. The size of the output is determined solely by the size of the input. So it seems to me that taken in its strict sense there are ...
7
votes
0answers
103 views

Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?

D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper "On Uniformity Within $\mathsf{NC^1}$" that the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$ ($\mathsf{FO}$ plus ...
5
votes
1answer
118 views

Inherent limitation of Switching Lemma for finer lower bounds

The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits. The Switching Lemma claims that we can get a ...
9
votes
0answers
153 views

Evaluation of bounded-depth circuits

Is the evaluation problem for $\mathsf{AC}^0_d$ circuits in $\mathsf{AC}^0_{d+1}$? What is the least depth $k(d)$ such that the evaluation of an $\mathsf{AC}^0_d$ circuits can be computed in ...
1
vote
1answer
135 views

Succinct Representation and Communication complexity

Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of ...
7
votes
0answers
100 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 ...
11
votes
2answers
378 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 ...
2
votes
0answers
122 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 ...
11
votes
1answer
157 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 ...
9
votes
0answers
402 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
136 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
137 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
385 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 ...
4
votes
0answers
366 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
227 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 ...
4
votes
1answer
212 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
101 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
370 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
228 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 ...
11
votes
2answers
446 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
294 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
144 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 ...