Questions tagged [circuit-complexity]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
344 views

Intuition on Lupanov's Upper Bound on Circuit Size

The following result, by Lupanov, is a classic in the theory of Boolean function complexity: Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
sdsdsd's user avatar
  • 133
5 votes
1 answer
386 views

Relation between ACC^0 and DTIME

In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$. How far can we potentially push this result? In other words, what is the largest $...
Nicholas Brandt's user avatar
1 vote
0 answers
51 views

Pfaffian orientation algorithm for planar graphs

I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related ...
Soham Chatterjee's user avatar
2 votes
0 answers
71 views

On the multiplicative overhead 2 in the construction of pairwise independent hashing from ERCs

A standard method of constructing pairwise independent hash function from error-correcting code is as follows: Given a generator matrix $G$ of a distance-$d$ linear error-correcting code mapping $m$ ...
Kagura Hitoha's user avatar
0 votes
0 answers
75 views

Original references for Karp-Lipton theorem improvement by Sipser

The Wikipedia article about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma_2=\Pi_2$), says the following: The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, ...
Nicola Gigante's user avatar
4 votes
1 answer
69 views

Does there exist constant overhead reduction between common cryptographic primitives?

I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
Kagura Hitoha's user avatar
10 votes
1 answer
299 views

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy? Couldn't find much in ...
J.Doe's user avatar
  • 468
5 votes
0 answers
59 views

W[t]-containment of partial covering problems

I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
xtyner's user avatar
  • 81
2 votes
0 answers
54 views

Intermediate problems between $CC^0$ and $ACC^0$

Definitions $CC^0[m]$ is the set of languages decidable by constant-depth polynomial-size circuits consisting only of unbounded-fanin $MOD_m$ gates. We write $CC^0$ to mean the union over all $m$. $...
Jake's user avatar
  • 1,204
3 votes
0 answers
91 views

Reference Request: Circuit Complexity Theory Course

I want to learn circuit complexity theory. I have found this book "Introduction to Circuit Complexity A Uniform Approach" by Heribert Vollmer. I have also found lecture notes of one course ...
Soham Chatterjee's user avatar
2 votes
1 answer
115 views

doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations. I follow the proof of the following two identities : $[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
emmy's user avatar
  • 123
0 votes
1 answer
197 views

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define $$ f_{\mathfrak S}(z) := \sum_{\...
dohmatob's user avatar
  • 291
3 votes
2 answers
160 views

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by \begin{eqnarray} \langle x,y\rangle_{\...
dohmatob's user avatar
  • 291
6 votes
0 answers
161 views

Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?

Background What is currently known for depth-2 $CC^0$ circuits with restricted gate types: In [1] it is shown that $(MOD_p)^k \circ MOD_m$ circuits (that is, $k$ layers of $MOD_p$ gates at the output)...
Jake's user avatar
  • 1,204
4 votes
0 answers
53 views

Quantum circuits vs quantum circuits w/ only local interactions?

If we restrict a quantum circuit to only have interactions between "nearby" qubits (for some connection topology that defines "nearby", as is the case in several actual quantum ...
Joshua Grochow's user avatar
4 votes
1 answer
109 views

NC0 randomnes vs. non-uniformity

In Ajtai and Ben-Or. A theorem on probabilistic constant depth Computations. STOC '84, 1984 Ajtai and Ben-Or show a non-uniform derandomization of BPAC0. Is there a similar relation known for ...
user68538's user avatar
0 votes
1 answer
152 views

What is the simplest one-way function (in terms of boolean circuit complexity)?

What is the simplest known one-way function? By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity). (I'm trying to find ...
Azuresonance's user avatar
8 votes
1 answer
230 views

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
user avatar
2 votes
1 answer
184 views

Value of studying boolean function complexity through circuits complexity nowadays

Apparently boolean function complexity analysis through circuit complexity has a limit (as they are natural proofs), and this means it is not possible to proof $P \not= NP$ unless there are no one-way ...
Wilmer Bandres Hernández's user avatar
1 vote
0 answers
106 views

Boolean formula complexity of arithmetic expressions

This is a followup question to this other question, where I was told that multiplication is in $NC^1$ so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a ...
Nicola Gigante's user avatar
5 votes
1 answer
306 views

Formula complexity of arithmetic multiplication

I'd need some bounds on the size of Boolean formulas (over $\land$, $\lor$ and $\neg$) computing the multiplication of two integers. I'm not an expert in circuit complexity and I'm crawling through ...
Nicola Gigante's user avatar
0 votes
0 answers
44 views

Do uniformity lower than DLOGTIME rlead to same result?

Maybe an answer to this Here input of length and position is binary rather than unary, so traditional "DLOGTIME-uniform" is now "O(n)-uniform". (If traditional "DLOGTIME-...
l4m2's user avatar
  • 111
2 votes
1 answer
134 views

Counting argument for LTF circuits

In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
Tulasi's user avatar
  • 327
8 votes
1 answer
145 views

Reductions and projections in circuit complexity

I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity. My understanding is that a ...
Noel Arteche's user avatar
0 votes
0 answers
96 views

Non-uniformity assumptions in circuit complexity

I recently came accross the following standard inclusion of complexity classes: $$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
Noel Arteche's user avatar
5 votes
1 answer
143 views

Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?

(copied from a mathoverflow question because I realized this may be more appropriate for it) Let $A_1,A_2,...,A_k$ be $N$-by-$N$ matrices, with indeterminate entries in some field (say real or complex ...
Matt Hastings's user avatar
3 votes
0 answers
89 views

Sparsity Bounds for Probabilistic Polynomials

Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority? A probabilistic polynomial is a distribution of polynomials $D$ such that ...
AnonTCS's user avatar
  • 71
1 vote
0 answers
135 views

Can NP-complete language be in $mP/poly$?

Can NP-complete language be in monotone $P/poly$?
qwerty43's user avatar
  • 111
2 votes
0 answers
74 views

Pebble games and conversions to bounded width circuits

Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits? Here, "conversions to bounded width circuits" means that circuits ...
Hiroki Morizumi's user avatar
5 votes
0 answers
112 views

Complexity of approximating boolean functions with circuits

Let $f$ be a boolean function on $n$ variables - say we want to find the smallest circuit $C$ where $C(x)=f(x)$ for all but an $\epsilon$ fraction of inputs $x \in \{0,1\}^n$. What is known about the ...
Igor Ferst's user avatar
2 votes
0 answers
67 views

Does advice reduce depth?

Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like "If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then ...
trillianhaze's user avatar
3 votes
1 answer
117 views

$\mathrm{AC}^0$ upper bound for Hamming weight

Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says: Any depth $d$ circuit that accepts all $n$ bit strings of Hamming weight $\frac{n}{2} + 1$ and rejects ...
AngryLion's user avatar
  • 173
5 votes
1 answer
163 views

$AC^0$[subexp] vs. NC

My question is about the possibility of trading size for depth in circuits. Under what conditions is it true (or, plausible) that $AC^0[2^{n^\delta}] \subseteq NC^i$ for some constants $\delta < 1, ...
zfkmz's user avatar
  • 187
5 votes
2 answers
211 views

Circuit uniformities more restrictive than $DLOGTIME$

Definitions: The "direct connection language" of a circuit family is the set of tuples $\langle t, a, b, y \rangle$, where $a$ and $b$ are node/gate numbers in the $n$th circuit in the ...
Jake's user avatar
  • 1,204
8 votes
1 answer
138 views

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for ...
Jake's user avatar
  • 1,204
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
2 votes
0 answers
101 views

Recovering the inputs to Boolean circuits after partial evaluation

This question discusses Boolean Circuits and Boolean functions from $n>1$ inputs to one Boolean output. Notation: $\textit{arity}(\mathcal{C})=n$ if $\mathcal{C}$ takes $n$ inputs, similarly for ...
ShyPerson's user avatar
  • 424
10 votes
1 answer
231 views

Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

Terminology $CC^0[m]$ is the set of polynomial-sized, constant depth circuits consisting entirely of $MOD_m$ gates for some $m \geq 2$, where a $MOD_m$ gate outputs a 1 if and only if the sum of its ...
Jake's user avatar
  • 1,204
-1 votes
1 answer
88 views

Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization. If instead we are given a partial truth table, and we just ...
yters's user avatar
  • 203
0 votes
0 answers
89 views

Useful primitives CPUs could provide, from TC0 (or NC1)

I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational ...
Thomas Klimpel's user avatar
3 votes
0 answers
118 views

Complete problems for $(NP\cap CoNP)/poly$ class and universal representations

It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform ...
Erfan Khaniki's user avatar
4 votes
0 answers
207 views

What does width $4$ permutation branching program correspond to?

$L$ can be computed by a family of programs over $S_3$ of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of polynomial size. $L$ can be computed by a family ...
Turbo's user avatar
  • 12.8k
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
1 answer
158 views

$ACC^0$ implementation of a boolean function

Consider the symmetric boolean function $$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$ It is implementable in $TC^0$. Is there an $ACC^0$ implementation? The reason I ask is there seems ...
User2021's user avatar
5 votes
0 answers
162 views

Trading treewidth for depth in Boolean circuits

We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is ...
ckamath's user avatar
  • 223
0 votes
0 answers
60 views

Is anything known about NC$^1$ with NP oracle

A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
Abdallah's user avatar
  • 803
1 vote
1 answer
96 views

Variable wire weights in DLOGTIME-uniform circuits

The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, ...
Jake's user avatar
  • 1,204
7 votes
2 answers
849 views

Why should we believe that $NEXP \not \subset P/poly$

I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
Mohsen Ghorbani's user avatar
12 votes
2 answers
326 views

Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $...
verifying's user avatar
  • 1,062
1 vote
1 answer
100 views

Composition theorem for randomized communication complexity

I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find $$ R_{1/4} (f \circ ...
exteral's user avatar
  • 113

1
2 3 4 5
8