# Questions tagged [circuits]

A computation model in which the computation is described via circuits of various logic gates.

256 questions
Filter by
Sorted by
Tagged with
79 views

### How can languages that are E-complete have sub-exponential size circuits?

The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results. ...
543 views

### Regular Languages in $\mathsf{\text{}NC^1}$

Theorem : To prove $\mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$. To prove the theorem stated above we need some theorems and definitions given below : Barrington Theorem : A branching ...
95 views

### How many bits we can negate using two/three NOT gates?

How many bits we can negate using two/three NOT gates ? I am newbie at this subject so I ask for help. It is about circuits. Edit After reading link given in comments by @D.W I think that I can ...
109 views

290 views

### Function that cannot be computed by a Boolean circuit of size $2^n/2n$

Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\}$ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a ...
1k views

### Given a Turing machine , How to construct a efficient boolean circuit?

The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page ...
106 views

### Given a function and its complexity, what is the complexity of its circuit?

For example, given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also ...
3k views

Input : Adjacency-list representation of Directed acyclic graph (Boolean circuit). see Complexity theory by Arora and bark, page no- 104 Find : Adjacency matrix representation of DAG (Boolean ...
245 views

### Computing snapshot of Turing machine from previous snapshots in logarithmic space?

To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105] Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^*$ be some input for $M$...
75 views

### $\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?

Now, I have the following conjecture. $\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$. However, I am at a loss at ...
689 views

### 3 bit binary multiplier?

I have the following 2-bit binary multiplier How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier? I notice that there are 2 half-adders, and there are a bunch of ANDs ...
157 views

### Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

Let me define the problems first Polynomial Identity Testing $(\mathsf{PIT\text{}})$ Given : A polynomial $p$ over some field $\mathbb{F}$. Decide : Are all coefficients of the monomials of $p$ ...
623 views

### Why do all recent SAT solvers work on CNF instead of circuit SAT?

After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG ...
198 views

### Size of constant depth circuit for digital comparator?

Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers? Two $n$-bit binary numbers can be compared using a digital ...
75 views

### Division circuit - problem

I have a question about the logic circuit performing the division ( http://userpages.umbc.edu/~squire/cs313_l20.html ). I implemented it to some software but does not work. I drew the schematic ...
124 views

### Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has ...
48 views

### Circuit of constant depth that takes three binary numbers and outputs two binaries?

How can I construct -- or better to say what type of circuit can be like this -- a circuit that takes 3 binary numbers (a, b, c) and then calculates two binary numbers (d, e) in a way that ...
99 views

### Is it possible to determine if C=A+B faster than adding A+B in logical circuits

With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B. I know that it is possible to just determine the longest the circuit ...
609 views

### Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?

Cause applying H (hadamard gate) on a state |0> will evolve to 50% |0> and 50% |1>, assuming we are meausring along the vertical axis (Z-axis). While applying a measurement along a horizontal axis (e....
83 views

111 views

### Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?

Sanjeev Arora and Boaz Barak show the following : $P/poly = \cup_{c,d} DTIME (n^c)/n^d$ where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$ and runs in $O(n^c)$ ...
44 views

### What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?

I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant ...
110 views

### On relation between FFT and polynomial multiplication

Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ ...
79 views

### Unconditional arithmetic circuit lower bounds for permanent/determinant

In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) ...
2k views

32 views

### What are the recent research directions in the topic of circuit lower bounds from derandomization?

I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this direction?...