Questions tagged [circuit-families]
The circuit-families tag has no usage guidance.
26 questions
40
votes
3
answers
3k
views
Circuit lower bounds over arbitrary sets of gates
In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis ...
- 13.9k
39
votes
3
answers
2k
views
Why are mod_m gates interesting?
Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.
What's so ...
- 11k
27
votes
2
answers
768
views
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.
A Boolean circuit is called an NC0k circuit ...
- 16.6k
22
votes
1
answer
701
views
Classifying reversible gates
Post's lattice, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the ...
- 13.9k
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
14
votes
1
answer
784
views
Circuits with oracles vs. Turing Machines with oracles
Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for ...
- 8,939
14
votes
1
answer
396
views
Small circuits for circuit evaluation problem
Let $\mathsf{CircuitEval}_{s, n}$ be the function which maps an $s$-gate circuit $C$ on $n$ bits and an $n$-bit string $x$ to $C(x)$. Assume that circuits are encoded as an acyclic sequence of ...
- 431
11
votes
1
answer
174
views
Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?
I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum ...
- 8,939
7
votes
1
answer
458
views
May Boolean circuits be exponentially more concise than Boolean formulae?
Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest ...
- 9,838
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
1
answer
210
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$ ...
- 255
5
votes
1
answer
2k
views
Simulating Turing machines (output included) with circuits
A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of ...
- 223
5
votes
2
answers
418
views
Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?
Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its ...
- 14.2k
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
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
4
votes
0
answers
90
views
About Boolean functions with a high sign-rank
Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
- 1,453
3
votes
1
answer
133
views
$\mathrm{AC}^0$ upper bound for Hamming weight
Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says:
Any depth $d$ circuit that accepts all $n$ bit strings of Hamming
weight $\frac{n}{2} + 1$ and rejects ...
- 193
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
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
2
votes
2
answers
292
views
Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?
This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = ...
- 3,888
2
votes
1
answer
366
views
Complexity of advice language?
Let $L$ be a language in P/poly. There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$. Consider the language $A(M)$ of all advice strings ...
- 19.2k
2
votes
2
answers
258
views
Reversible Logic Circuit Synthesis [closed]
I am about to choose a project regarding "Reversible logic circuit synthesis". I've studied well about "Switching circuits and Logic design" and I found it very intriguing but I've got no idea about ...
- 121
2
votes
0
answers
171
views
Satisfiability of circuits with infinite input
As we all know, satisfiability of Boolean circuits is NP-complete.
I am wondering if there are any studies of circuits with infinite inputs?
That is, suppose the input is from the set $\{0,1\}^\omega$...
- 5,636
1
vote
0
answers
189
views
Problems or issues with a proposed circuit class?
I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where ...
- 227
0
votes
1
answer
94
views
DC uniform circuit and parity-P
This is a question from the lecture about Toda's theorem:
http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps
The lecture uses theorem 1 and theorem 2 but not include proof. ...
- 83
-3
votes
1
answer
285
views
Some questions about the depth hierarchy for threshold circuits [closed]
(I am hugely editing the question. My initial question was if lowerbounds on threshold circuits say anything about P/NP and it seems that they dont. Irrespective of P/NP its an independently true fact ...
- 1,453