# Questions tagged [circuits]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
1 vote
82 views

482 views

1 vote
238 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 ...
123 views

147 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 ...
244 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 ...
95 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 ...
243 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 ...
376 views

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 0 answers 105 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 0 answers 217 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 1 answer 558 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$... 190 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 ...