# Questions tagged [circuits]

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

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
79 views

36 views

### Circuit complexity of random Boolean functions

I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why ...
37 views

### Does Cook and Ruzzo's result also hold for logspace-uniform AC0?

In Cook's famous paper on $\mathsf{NC}$, he cites the following result: PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those problems solvable by uniform unbounded fan-in ...
35 views

### Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
56 views

### Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
53 views

### How to minimize the number of gates of an arithmetic circuit?

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and ...
177 views

### Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
38 views

### From SETH to circuit lowerbounds

Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR) In threshold ...
31 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?...
172 views

### AC0 and first order logic equivalence

The page on descriptive complexity theory in Wikipedia states the following: "First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of ...
78 views

### Class of languages recognizable by n-bit formulas of size at most $T(n)$

A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT nodes fan-...
42 views

20 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
37 views

### Equality checking mod $10$ via arithmetic circuits

I'm interested in implementing equality checking mod 10 in an arithmetic circuit. Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it ...
24 views

### projection of arithmetic formulas to determinant

I am looking for a direct proof (i.e. without going through ABPs) that if $f(\bar{x})$ has an arithmetic formula of size $s$ then it is a projection of an $O(s)\times O(s)$ determinant. It seems ...
17 views

### What standardized formats (if any) exist for boolean circuits?

Being able to represent a Boolean circuit is useful in a number of areas of Computer Science, such as Circuit Satisfiability, Zero-Knowledge Proofs and Garbled Circuits. Are there any standards for ...
39 views

### About sign-rank of Boolean functions

Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?
85 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 ...
564 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 ...
149 views

### On power of $P/poly$

(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close? (2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the ...
27 views

### Arithmetic problems known to be in TC^{i+1} but not known to be in TC^i

Is there an arithmetic problem that is known to be in $TC^{i+1}$ but not known in $TC^i$ for any $i\geq0$? Concrete examples for $i=0$ would be of most utility however any arithmetic example is fine.
46 views

### Does an Expression in RPN Give us a Linear Way of Writing What Happens in a Circuit?

I mean, say we want to show how we can implement an OR gate in terms of a NAND gate. If we write in Polish notation, then we've suggested that the circuit takes the gates before the inputs. If we ...
58 views

### How do I triangularise a netlist?

I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
119 views

### Simplifying circuits using boolean algebra

I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated. I have y'+z+w'x+wx' I feel like I could use DeMorgan'...
41 views

### Is VHDL a description language for a Boolean circuit or are both concepts unrelated

I am looking for a way to translate basic c programs (subset of c or java or some declarative programming language) to a Boolean circuit. I know that Turing machines are reducible to Boolean circuits ...
143 views

### Functional Unit and Micro-operations Schematics

I'm sitting an exam on Computer Architecture in a few days and i'm stuck on a particular type of question. I'm asked to: Provide a detailed schematic for a functional unti that implements the ...
174 views

### Show that problem is PSPACE-complete - path in directed graph

I have a following problem: Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
8 views

### Circuit : Switching function. Can I ignore RESET and CLOCK for the functions?

So if I have to state any function like state transition function or switching function can I ignore CLOCK and RESETS?
15 views

### Simulating Boolean Circuit with RAM

Statement: Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM). Could you please supply me with a reference to an ...
20 views

### Which gates are “pre computation” universal?

In the following, by “functions” I will mean 2 input 1 output Boolean logic functions (for conciseness). A function is called “universal” if by using it (sometimes multiple times, chained together), ...
26 views

22 views

### Boolean circuit size of $i$th bit of determinant?

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. Is there a polynomial size boolean circuit for $i$th bit of ...
19 views

### Constucting QAP in the pinoccho paper

In this paper Pinocchio: Nearly Practical Verifiable Computation, on page 3 there is a way to construct the QAP and example doing it. Question : they say We pick an arbitrary root rg ∈ F for ...
38 views

### Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
19 views

### Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits

I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is ...
35 views

### Circuit Lower bound for $EXP^{NP}$

By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$. Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures). By using the ...
91 views

### circuit for finding the index of first zero entry in a binary string

finding the index of first zero entry in a binary string: Input: binary string ($0$'s and $1$'s) Output: index of first zero entry Can you give a circuit for finding the index of first zero entry ...
68 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 ...
94 views

### 2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
Let $c ∈ ℕ₊$ be constant and $p∈\{0,1\}^c$ a fixed bitpattern of width $c$. Let us assume that the input length is structured as a list of blocks $b_1 … b_n$, each block having width $c$; is it ...