Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.

6
votes
0answers
73 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 $\...
4
votes
0answers
68 views

Asymptotic complexity of mass production

For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1). Let $k{\times}f : \{0,1\}...
0
votes
0answers
47 views

Modular and multiplication operations

Does modular operation reduce to integer multiplication integer multiplication reduce to modular operation in fully linear time and/or in logarithmic time on linear number of processors?
1
vote
0answers
207 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 ...
9
votes
0answers
95 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_{...
8
votes
1answer
246 views

Nondeterminism is on average useless for circuits?

Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result. Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
2
votes
0answers
39 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 ...
6
votes
0answers
116 views

Number of circuits computing a given function

Let's say we have some function that can be computed by a minimal circuit of size $m$ (using some metric, say, the number of gates). Other than this minimal circuit, there will be many other circuits ...
4
votes
0answers
72 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 ...
1
vote
0answers
96 views

Is there any NC-complete problem with respect to logspace reduction?

The question is on the title. We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
4
votes
0answers
58 views

Can an efficiently computable non-one way permutation be written as the composition of polynomially many easy to compute involutions?

Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at ...
7
votes
0answers
158 views

Can every efficiently computable permutation be written as the composition of two efficiently computable involutions?

It is well-known that every permutation can be written as the composition of two involutions. Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\...
10
votes
3answers
567 views

What are examples of how non-uniformity can be useful?

I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that ...
0
votes
0answers
71 views

Why is the circuit class ACC0 important as a mathematical structure? [duplicate]

I agree that ACC0 is a good toy object to study before trying to understand more complicated circuit classes. But here I'm more looking for a mathematical reason, rather than a practical one. What ...
3
votes
3answers
440 views

Why is the circuit class AC0 unavoidable?

Take AC0. What is a natural thought process that leads to the definition of AC0? Does this class arise intrinsically anywhere? My problem is that in the case of unbounded fan-in, AND and OR gates ...
0
votes
0answers
47 views

Can you find a function which is far easier than it is approximately symmetric?

Define $\mathcal{F}(G) = \{ f : \{0, 1\}^n \rightarrow \{0, 1\} \mid G \leq Aut(f) \}$. Note that all functions can be computed on $n$ bits with circuits of size $2^n/n$. On the other hand, we don't ...
3
votes
1answer
137 views

Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-...
4
votes
0answers
113 views

Is $L\subset NC^1$

Arora and Barak's online book claims in exercise 6.11 that $NC^1=L$. While the $NC^1\subset L$ direction is relatively straightforward and explained in many other texts, I couldn't prove or find the $...
6
votes
0answers
127 views

Has what I am calling “helpfulness” here been studied?

We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
1
vote
2answers
207 views

Efficiently computable by a “simple” algorithm?

I am interested in the relation between "program complexity" and "computational complexity". In particular, I was wondering What is known about the minimal length a program must have to solve a ...
4
votes
1answer
116 views

Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$. We know from Boppana's 1997 paper on the average sensitivity of ...
2
votes
0answers
48 views

Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?

Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
2
votes
0answers
72 views

Scaled down and scaled up versions of Impagliazzo-Wigderson Therem

A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP. When can we change $P$ with some ...
1
vote
0answers
102 views

Solving 0/1 integer programming and solving ACC-of-SYM circuits

I am referring to the proof of Theorem 1.4 in this STOC 2014 paper, https://arxiv.org/abs/1401.2444. In particular my question is about the argument that begins in the 8th line of page 9 where the ...
1
vote
0answers
88 views

Possibly small circuit complexity class containing REG?

What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}? If we believe Theorem 2 in Koucký, Circuit Complexity of ...
-5
votes
1answer
117 views

Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$. Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$? Suppose if it turns out that $\...
14
votes
1answer
172 views

What are the consequences of $P \subseteq L/poly$?

A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice. See here for more info: https://en.wikipedia.org/wiki/L/poly ...
2
votes
1answer
94 views

Complexity of maximising weighted sum of and functions on a set of binary variables

Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land x_k$$ in which ...
4
votes
0answers
165 views

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$. For more info, see "Superpolynomial circuits, almost sparse oracles ...
14
votes
2answers
422 views

OR-circuit complexity of a dense linear operator

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
0
votes
0answers
146 views

On $i.o.P/poly$?

Is $NEXP^{NP}\not\subseteq i.o.P/poly$? Is there any consequence if $NP$ or $PP$ is in $i.o.P/poly$? Showing $NEXP^{NP}\not\subseteq P/poly$ needs Karp-Lipton. What is the best $i.o.P/poly$ ...
5
votes
0answers
93 views

Non-Uniform Classes of Languages not Closed Under Complement

Most "normal" non-uniform circuit classes are closed under complement. Just add a negation gate to the output of a circuit, and if necessary, apply De-Morgan's law. Now there are some natural non-...
1
vote
1answer
123 views

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

Lets define the class $ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \...
0
votes
1answer
184 views

What do stronger circuit lower bounds give in terms of derandomization?

We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$. This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
27
votes
0answers
605 views

Is BPP= P known for ANY uniform model of computation?

Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson. ...
2
votes
1answer
95 views

Non-Uniform Lower Bounds for NSPACE

If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$ where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of ...
1
vote
0answers
52 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the ...
0
votes
0answers
19 views

On $PP$, $MP$ and $\oplus P$ classes?

In here $PP^{\oplus P}\subseteq MP$ is shown and it is left as an open problem on whether $MP=PP^{\oplus P}$. $MP\subseteq P/poly$ collapses the polynomial hierarchy and $PH\subseteq P/poly^{\oplus P}...
12
votes
1answer
461 views

Is BPP vs. P a real problem after we know BPP lies in P/poly?

We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold. The "/poly" means that we work non-...
-3
votes
1answer
182 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 ...
8
votes
0answers
97 views

Reference for a circuit lower bound for slightly superexponential time

It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem. My question is ...
3
votes
1answer
125 views

Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

Getting Started Consider a parameterized problem $F$. We use $n$ to denote the input size and $k$ to denote the parameter. Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{...
7
votes
0answers
147 views

Complexity Class Equalities on the Edge of Inconsistency

What are some of the most extreme potential equalities between computational complexity classes (especially if there is a barrier to refuting them)? These may give us an opportunity to prove better ...
3
votes
0answers
159 views

Circuit's with gate computing only “simple” functions

I was curious if something like that is known or was studied. Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$. Now let's ...
6
votes
0answers
111 views

Are there generalizations for Chow's theorem?

The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients. Are there other circuits for which ...
17
votes
1answer
529 views

Example demonstrating the power of non-deterministic circuits

A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts ...
1
vote
1answer
77 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 ...
10
votes
1answer
428 views

Deciding the Most Significant Bit of Binary Multiplication

I am interested in determining the complexity of the following decision problem: Given two integers $l_1$ and $l_2$ (each with at most m bits), decide whether the most significant bit of the ...
3
votes
1answer
59 views

parallel algorithms for the determinant of the Hessenberg matrix

I am interested in highly parallel algorithms for computing the determinant of matrices of a special form (over finite fields). It is known that computing determinant of general matrices over finite ...
10
votes
2answers
400 views

High-level overview of Razborov's method of approximations

What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind it?