Tagged Questions

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

learn more… | top users | synonyms

16
votes
0answers
276 views

Why is HAMILTONIAN CYCLE so different from PERMANENT?

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
2
votes
0answers
45 views

What is the strongest known lower bound against SIZE(n)?

What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
0
votes
0answers
43 views

Depth-three arithmatic circuit for parity [closed]

I need to construct a depth-three arithmetic circuit for parity (with using less than O(2^n) gates.. I've managed to write a 4-depth circuit dividing the inputs into $\sqrt(n)$ groups, calculating the ...
20
votes
1answer
279 views

Arithmetic circuits with just one threshold gate

When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add one fanin-1 ...
7
votes
1answer
116 views

“Largest” class properly contained in PSPACE for a random oracle

Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly ...
15
votes
1answer
415 views

Any polynomial which is hard to count but easy to decide?

Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial ...
3
votes
1answer
112 views

Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
11
votes
1answer
135 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
18
votes
3answers
423 views

What is the minimum size of a circuit that computes PARITY?

It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp. (We define size as the number of AND and OR ...
10
votes
2answers
256 views

Minimum Tree-width of circuit for MAJORITY

What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ? Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$. I care ...
13
votes
0answers
183 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the ...
6
votes
2answers
334 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
5
votes
0answers
39 views

Boolean circuit for efficient array indexing

Suppose that I have an array $\{a_i\}$ of $n$ elements, each $k$ bits wide, and an array $\{b_i\}$ of $n$ elements, each $\lceil\log_2n\rceil\le k$ bits wide. I need a boolean circuit which will ...
11
votes
0answers
148 views

Lower bounds for the size of nondeterministic circuits

It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method. Recently, I noticed that the ...
6
votes
0answers
69 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
4
votes
1answer
224 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
2
votes
0answers
24 views

Lower bounds in PRAM model for evaluation of straight-line code

Miller, Ramachandran and Kaltofen showed that any straight line program can be executed in parallel time O(log n) using M(n) processors where M(n) is the number of processors for multiplying nxn ...
13
votes
1answer
254 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of ...
4
votes
1answer
68 views

Commitment schemes with verification in NC0

Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$? If so, what is the minimum possible depth of the circuit for verification? Applebaum ...
10
votes
1answer
155 views

Do we have any nontrivial uniform circuits?

Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$. On the other hand, it might be that ...
5
votes
1answer
237 views

A good exposition of the random restriction method

I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different ...
9
votes
1answer
159 views

Random restrictions and the connection to total influence of Boolean functions

Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ ...
8
votes
1answer
287 views

Fewest number of gates for Multiplication

What is the best result for the number of gates in a circuit multiplying two n-bit integers? The obvious method generates $\theta(n^2)$ gates. There are better approaches with $\theta(n\log n ...
3
votes
0answers
64 views

Non-boolean monotone planar circuit value problem

It is known that monotone planar boolean circuits have a NC circuit value problem (in fact, much more is known). What about non-boolean monotone planar circuits? Precisely, take $Q=\{0,...,n-1\}$ ...
12
votes
3answers
400 views

Good text on introduction to circuit complexity

I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.
17
votes
2answers
318 views

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has ...
5
votes
0answers
85 views

Is computational complexity of neural networks so old-fashioned?

I find that works on computational power and complexity of neural nets are all from 1980s/1990s or even earlier. Surveys and books are also from that time. Personally, I find problems in this field ...
10
votes
0answers
142 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 ...
25
votes
2answers
678 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
109 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
134 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. ...
8
votes
1answer
278 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
771 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?
12
votes
2answers
185 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
153 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
95 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 ...
11
votes
1answer
262 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 ...
6
votes
2answers
352 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
150 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
93 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
317 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
135 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 ...
8
votes
1answer
173 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
191 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 = ...
7
votes
0answers
219 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 ...
12
votes
1answer
227 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
187 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 ...
13
votes
0answers
321 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
433 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 ...
13
votes
0answers
225 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: ...