Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
4 votes
1 answer
119 views

Constructing vector valued boolean circuits from boolean circuits

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n >...
Martin Berger's user avatar
2 votes
1 answer
88 views

planar circuit logspace completeness

In https://dl.acm.org/doi/pdf/10.1145/1008354.1008356, a proof is given for PCV is log space complete. I do not understand the construction though, a circuit is given but it is not clear to me what is ...
redrobinyum's user avatar
3 votes
0 answers
74 views

What is the actual difference between uniformity conditions for NC¹

I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for $k\geq 2$ $NC^k$ the uniformity conditions are equivalent, but for NC¹ they are not. I am ...
lzrdnb's user avatar
  • 31
12 votes
1 answer
477 views

Trade-off for Barrington's theorem

Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
Michael Lampis's user avatar
5 votes
0 answers
58 views

How to prove that all pairwise independent hashing circuits are superconcentrators?

It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
Kagura Hitoha's user avatar
3 votes
0 answers
75 views

What is $\mathrm{NC}^0$-uniform reduction

I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages. Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
Alexey Milovanov's user avatar
3 votes
1 answer
396 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
422 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
55 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
3 votes
0 answers
76 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
81 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
5 votes
1 answer
74 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
319 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
62 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
55 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,214
3 votes
0 answers
107 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
121 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
203 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
165 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
165 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,214
4 votes
0 answers
60 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
115 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
155 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
244 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
200 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
111 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
313 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
141 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
153 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
100 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
146 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
96 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
136 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
78 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
123 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
123 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
166 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
236 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,214
8 votes
1 answer
139 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,214
3 votes
0 answers
106 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
3 votes
0 answers
106 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
  • 434
10 votes
1 answer
234 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,214
-1 votes
1 answer
89 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
95 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
121 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
228 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.9k
8 votes
1 answer
234 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
  • 9,419
3 votes
1 answer
161 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

1
2 3 4 5
8