# Questions tagged [circuits]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
103 views

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_{... 0answers 95 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 ... 0answers 270 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 ... 0answers 77 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 ... 0answers 109 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$... 0answers 47 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 ... 0answers 47 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)\... 0answers 44 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 ... 0answers 61 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\}^...
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 ...
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 ...