All Questions
Tagged with circuit-families cc.complexity-theory
15 questions
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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