# Questions tagged [circuit-complexity]

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

313 questions
415 views

### What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the Karp-...
385 views

141 views

### Non-boolean monotone planar circuit value problem

It is known that monotone planar boolean circuits have a NC circuit value problem (in fact, much more is known). What about non-boolean monotone planar circuits? Precisely, take $Q=\{0,...,n-1\}$ ...
771 views

### Good text on introduction to circuit complexity

I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.
492 views

### Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has ...
177 views

### Is computational complexity of neural networks so old-fashioned?

I find that works on computational power and complexity of neural nets are all from 1980s/1990s or even earlier. Surveys and books are also from that time. Personally, I find problems in this field ...
197 views

### Approximating $\textrm{AC}^{0}$ by sparse polynomials

Let $f$ be a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}$. We say that $f$ is randomly approximated with error probability $\epsilon$ by a family of polynomials $P$ if \forall x\...
953 views

### Kolmogorov's conjecture that $P$ has linear-size circuits

In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
121 views

### A possible application of TCS to EE: disruption-resistant circuits

Consider the following problem. We're given a circuit $C$ with $n$ binary inputs and $n$ binary outputs, computing some boolean function $f_C : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$. We assume ...
150 views

### A curious Wilf equivalence class of function compositions

I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero: 1, 1, 6, 87, 2200, 84245. ...
303 views

### Lower bounds on monotone space complexity

The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by ...
814 views

### Terminology for f(g(x)) = g(f(x))

There is a paper by Ritt from 1923 that calls the relation, $f(g(x)) = g(f(x))$, permutable functions. Is there a more recent terminology used in the literature, or is this still the standard?
246 views

368 views

### Fundamental assumptions in complexity analysis

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM....
260 views

### Sketch of Razborov's paper “On the method of approximations”

(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
334 views

### Boolean Functions Where Sensitivity Equals Block Sensitivity

Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ ...
201 views

260 views

### Size hierachy for uniform circuits

There is the size hierarchy theorem for non-uniform circuits. Do we have any size hierarchy theorem for any kind of uniform circuits ? (By uniform here, I mean DLOGTIME uniform. But I don't know ...
424 views

### Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a ...
174 views

### The size of output in circuit complexity

In circuit complexity we have one circuit for each input size. The size of the output is determined solely by the size of the input. So it seems to me that taken in its strict sense there are ...
153 views

### Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?

D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper "On Uniformity Within $\mathsf{NC^1}$" that the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$ ($\mathsf{FO}$ plus ...
The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits. The Switching Lemma claims that we can get a ...