Questions tagged [circuits]
The circuits tag has no usage guidance.
3
votes
0answers
90 views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
2
votes
0answers
44 views
Is topological conventional computation possible?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f)\circ(f\times \mathrm{Id}_{X})=(\mathrm{Id}_{X}\times f)\...
11
votes
1answer
186 views
How small can be a layered boolean circuit for a function with circuit complexity $s$?
Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\...
3
votes
0answers
44 views
Do there exists reversible gate sets of intermediate growth?
Suppose that $f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions.
For all $n\geq r$, let $G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by
i. the ...
-2
votes
1answer
48 views
How to construct a branching program for a given function or formula?
Can someone throw some light on how to create a branching program from a given function? I have followed the definition of $BP$ on wiki and here. But I could not find any way to convert a function to $...
1
vote
0answers
217 views
Impagliazzo lemma, unclear detail in its proof
In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...
9
votes
0answers
97 views
Expected value of the evaluation of Boolean circuits of depth $2n$
I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.
Let $C_{...
2
votes
0answers
41 views
Arithmetic circuits with restrictions on occurrence of pairs of variables
I am curious if the following model was studied or has some obvious lower bounds:
We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going ...
4
votes
0answers
75 views
Circuits computing functions of inputs smaller than $n$
The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the ...
2
votes
0answers
59 views
Can we compute encodings of binary strings under arbitrary permutation groups?
Given a permutation group $G \leq S_n$, can you construct non-uniformly a circuit computing a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log|\{0, 1\}^n/G_n|)}$ with size $O_n(\frac{|\{0, 1\}^...
4
votes
2answers
140 views
Is there any notion of sensitivity for probabilistic Boolean functions?
Sensitivity is defined here. Denoting the neighbors of $x$ in the Boolean cube as $N(x)$, we define the sensitivity to be $s(f, x) = \sum_{y \in N(x)} I(f(x) \neq f(y))$, where $I$ is $1$ if the ...
-3
votes
1answer
188 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
vote
1answer
79 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 ...
7
votes
1answer
218 views
Has there been a study of circuits operating on arrays?
Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
9
votes
1answer
271 views
Evaluate boolean circuit on batch of similar inputs
Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.
Let $x \in \{0,...
5
votes
0answers
92 views
Switching between representations of boolean functions between circuits and Fourier expansions
I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this excellent resource
There, boolean functions are represented as linear ...
0
votes
0answers
169 views
Greater-Than operator using an Arithmetic Circuit
How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?
Where $x$ is the input to the ...
12
votes
1answer
437 views
Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?
I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”.
On the bottom of page 2 they remark that the results of Kannan imply that $...
2
votes
1answer
169 views
Piecewise Linear Circuit Identity Testing
A circuit is used to express a piecewise linear function of one variable $\ f:\mathbb{Q}\to\mathbb{Q}$ The component gates are:
add the outputs of two other gates together
scale the output of one ...
5
votes
0answers
260 views
Sketch of Razborov's 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
2answers
417 views
P/poly vs NP separation based on circuit trees instead of DAGs
there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast,
are there theorems/conjectures that relate P/...
