Questions tagged [circuits]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
82 views

$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]

We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
Soham Chatterjee's user avatar
0 votes
0 answers
60 views

Size vs. Time Hierarchy Theorems

I'm struggling with the following idea, but I cannot see where my mistake is. We know, from the Time Hierachy Theorems, that there are problems that require, say, double exponential time to decide. ...
Noel Arteche's user avatar
0 votes
1 answer
171 views

Can we do computing without electricity?

If electricity was never discovered, could we still make funcional computers to perform some level of useful tasks? Or won't we be able to build anything comparable in terms of computer power?
Joe DiNottra's user avatar
0 votes
0 answers
52 views

Solving sampling problems with circuits?

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
trillianhaze's user avatar
0 votes
0 answers
128 views

Boolean logic: What is the name of this trick to replace explicit negations by implications?

Consider a Boolean circuit $C$ composed of some finite set of input variables $A_1,\ldots, A_n$ and the connectives $\lor\land\neg\rightarrow$ (with $X\rightarrow Y=\neg X\lor Y$) (update: assume that ...
Duyal Yolcu's user avatar
3 votes
0 answers
105 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 ...
Samuel Schlesinger's user avatar
8 votes
1 answer
223 views

Monotone circuit representations of paths in a graph?

Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
a3nm's user avatar
  • 8,896
3 votes
0 answers
109 views

Improving boolean circuits w.r.t. a probability distribution

This is a reference request. Consider the following problem on boolean circuits [ 1 ]: Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$. Task: Find one or more ...
Martin Berger's user avatar
-1 votes
1 answer
83 views

How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]

I need to know for each of the $2^{2^3}$ boolean functions with $3$ inputs the smallest boolean circuit made only of NAND gates computing it (smallest in terms of the number gates). I would be glad ...
dnn's user avatar
  • 1
2 votes
1 answer
97 views

Correlation between noise resilience and output distribution of Boolean circuits

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at ...
cvalkan's user avatar
  • 31
1 vote
1 answer
823 views

How to build comparison operator (comparator) in an arithmetic circuit

I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to ...
user53169's user avatar
3 votes
2 answers
443 views

Is the unbounded fan-in model realistic?

Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates? As I understand, standard silicon ASICs ...
Randomblue's user avatar
7 votes
1 answer
199 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$...
Michael Wehar's user avatar
2 votes
0 answers
55 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)\...
Joseph Van Name's user avatar
11 votes
1 answer
482 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 $\...
Geoffroy Couteau's user avatar
5 votes
1 answer
122 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 ...
Joseph Van Name's user avatar
-2 votes
1 answer
158 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 $...
chelsea's user avatar
  • 111
1 vote
0 answers
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 ...
user2925716's user avatar
9 votes
0 answers
123 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_{...
J.-E. Pin's user avatar
  • 4,771
2 votes
0 answers
53 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 ...
ivmihajlin's user avatar
4 votes
0 answers
80 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 ...
user2316602's user avatar
2 votes
0 answers
70 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\}^...
Samuel Schlesinger's user avatar
4 votes
2 answers
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 ...
Samuel Schlesinger's user avatar
-3 votes
1 answer
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 ...
gradstudent's user avatar
  • 1,443
2 votes
1 answer
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 ...
gradstudent's user avatar
  • 1,443
6 votes
1 answer
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 ...
einpoklum's user avatar
  • 173
11 votes
1 answer
376 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,...
D.W.'s user avatar
  • 11.7k
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 ...
anaboolguest's user avatar
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 ...
Bush's user avatar
  • 241
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 $...
user avatar
2 votes
1 answer
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 ...
Gilbert Bernstein's user avatar
5 votes
0 answers
292 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 ...
vzn's user avatar
  • 11k
4 votes
2 answers
545 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/...
vzn's user avatar
  • 11k