Questions tagged [circuit-depth]
The circuit-depth tag has no usage guidance.
31 questions
12
votes
1
answer
520
views
Trade-off for Barrington's theorem
Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
- 3,722
3
votes
0
answers
90
views
What is $\mathrm{NC}^0$-uniform reduction
I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages.
Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
- 2,023
3
votes
0
answers
81
views
On the multiplicative overhead 2 in the construction of pairwise independent hashing from ERCs
A standard method of constructing pairwise independent hash function from error-correcting code is as follows:
Given a generator matrix $G$ of a distance-$d$ linear error-correcting code mapping $m$ ...
- 161
1
vote
0
answers
69
views
Circuit depth of linear algebra operations
I was checking the following paper [1] about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not ...
- 161
2
votes
1
answer
136
views
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations.
I follow the proof of the following two identities :
$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
- 123
5
votes
1
answer
250
views
What circuit depth is enough to compute a log-space complete problem?
To the best of my knowledge it is unknown that $\mathsf{L}$ is subset of $\mathsf{NC}^1$.
(Here $\mathsf{NC}^1$ is the class of decision problems solvable by a family of Boolean circuits, with ...
- 2,023
4
votes
0
answers
116
views
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$).
Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
- 2,023
0
votes
1
answer
83
views
In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$
I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that
Let $f$ be an n-variate degree d polynomial ...
- 280
2
votes
0
answers
69
views
Does advice reduce depth?
Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like
"If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then ...
- 121
5
votes
1
answer
173
views
$AC^0$[subexp] vs. NC
My question is about the possibility of trading size for depth in circuits.
Under what conditions is it true (or, plausible) that $AC^0[2^{n^\delta}] \subseteq NC^i$ for some constants $\delta < 1, ...
- 307
3
votes
0
answers
108
views
Do random functions have synchronous, alternating circuits with non-injective first layers?
After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
- 1,582
4
votes
0
answers
221
views
On solving Planar Circuit SAT
This enquiry is three-sided.
Side 1 - State of the art
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
- 6,912
4
votes
0
answers
133
views
Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?
The Complexity Zoo includes the class QNC$^0$, which does not seem to be a class of decision problems. When I chase the references of the link provided, they say
“To extend this definition from ...
- 4,495
2
votes
0
answers
134
views
What is the communication complexity of approximating addition?
In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...
- 653
8
votes
0
answers
532
views
How many different proofs are there of parity is not in AC0?
The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
- 81
2
votes
1
answer
98
views
Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994
This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636
So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
- 1,453
3
votes
1
answer
114
views
About the sign-rank of the Minsky-Pappert function
Apologies this might be a very trivial thing I am getting confused by!
Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ...
- 1,453
3
votes
0
answers
105
views
Fixed parameter Integer Programming circuit depth complexity
It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.
If implemented as an arithmetic circuit ...
- 13.3k
5
votes
0
answers
105
views
Using epsilon biased sets for circuit lower bounds
I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to ...
- 1,453
6
votes
1
answer
826
views
OR-weft Hierarchy
Say that a node of a circuit is small if it has fan-in at most 2 and large if it has fan-in greater than 2. The weft of a circuit is the maximum number large nodes in any path from an input node to an ...
- 1,072
5
votes
0
answers
421
views
About the ``recent" paper by Razborov in the Annals of Mathematics
Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the ...
- 1,453
9
votes
0
answers
207
views
Wide and shallow circuits for $\mathrm P$
The $\mathrm{NC} \stackrel?= \mathrm P$ question is not as famous as the $\mathrm P$ versus $\mathrm{NP}$ problem, but still a deep and interesting question. It is generally accepted that there are ...
- 8,939
9
votes
1
answer
612
views
Circuity complexity: monotone circuit of Majority function
As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+...
1
vote
1
answer
201
views
Is unbounded quantum fanout operation experimentally feasible?
It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf).
In particular, it is known ...
- 117
12
votes
0
answers
291
views
Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2
Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$...
17
votes
1
answer
523
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 any ...
- 1,405
16
votes
3
answers
6k
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 ...
- 679
10
votes
0
answers
278
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 $poly(...
- 21.8k
20
votes
2
answers
646
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 ...
- 5,793
11
votes
2
answers
446
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}(...
- 21.8k
19
votes
1
answer
775
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 ...
- 21.8k