Skip to main content
11 votes

Evaluate boolean circuit on batch of similar inputs

I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how: First of all, while ostensibly ...
Andrew Morgan's user avatar
9 votes

Is Circuit Minimization $P$-hard under logspace reductions?

The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
Eric Allender's user avatar
9 votes

How small can be a layered boolean circuit for a function with circuit complexity $s$?

As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers. A circuit is called synchronous (Harper 1977) if ...
Alex Golovnev's user avatar
4 votes

Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that $$ \Pr_g[\Pr[f=g] ...
Yuval Filmus's user avatar
  • 14.5k
3 votes

Can we do computing without electricity?

Short answer: yes, there are many "computers" which run without "electricity" (in the way most computers do nowadays). Read about Mechanical Computers, and more generally about ...
J..y B..y's user avatar
  • 2,776
3 votes

Monotone circuit representations of paths in a graph?

I still do not have any ideas about the general answer to this question, but I think I have an argument against the possibility to construct such a circuit in so-called monotone "decomposable ...
a3nm's user avatar
  • 9,517
3 votes

Do there exists reversible gate sets of intermediate growth?

If you allow ancilla bits (which is more natural from the computational perspective, see, e.g. the third paragraph of Section 1.2 of Aaronson-Grier-Schaeffer), then the answer is no. In fact, I ...
Joshua Grochow's user avatar
2 votes

Is there any notion of sensitivity for probabilistic Boolean functions?

I'm not sure if this is the generalization you have in mind, but a natural one is, if $p_x := \Pr[f(x) = 1]$, \begin{align} s(f,x) &= \sum_{y\in N(x)} D_{TV}(p_x,p_y) \\ &= \sum_{y\...
usul's user avatar
  • 7,615
2 votes

Is there any notion of sensitivity for probabilistic Boolean functions?

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity: $$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \...
Bjørn Kjos-Hanssen's user avatar
2 votes

Some questions about the depth hierarchy for threshold circuits

In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$...
Ryan Williams's user avatar
2 votes

Has there been a study of circuits operating on arrays?

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-...
Nikhil's user avatar
  • 1,364
2 votes

How to build comparison operator (comparator) in an arithmetic circuit

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty ...
Mark Schultz-Wu's user avatar
1 vote

Constructing vector valued boolean circuits from boolean circuits

I doubt it. At least, not in all cases. Suppose that you are working in a circuit model where every function $\mathbb{B}^k\to\mathbb{B}$ can be represented by a circuit with $\le 2^k+1$ gates, say by ...
D.W.'s user avatar
  • 12.2k
1 vote

Is the unbounded fan-in model realistic?

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .
Bjørn Kjos-Hanssen's user avatar
1 vote

How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it

For 3 inputs it's not $2^3$ functions but $2^{2^3}$ functions. Circuit minimization is generally hard. You could try using the aiger package, which will give you a circuit but ...
Mikolas's user avatar
  • 1,322
1 vote

Correlation between noise resilience and output distribution of Boolean circuits

I have found some hints on my question in Moshe Looks, Competent Program Evolution, p. 31: Most local perturbations of large random formulae have no effect – 96% of them for arity five, and 91% for ...
cvalkan's user avatar
  • 31
1 vote

How to construct a branching program for a given function or formula?

Even though I agree that this is not the right place to ask this question, you might want to look into the following book that contains everything about branching programs that you every wanted to ...
smengel's user avatar
  • 176

Only top scored, non community-wiki answers of a minimum length are eligible