# Tag Info

Accepted

### 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 ...
• 1,429
Accepted

### 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 ...
• 2,076
Accepted

### 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 ...
• 2,247

• 4,485

### 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 ...
• 27.5k

### 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-...
• 1,364

### 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 ...
1 vote
Accepted

### 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 ...
• 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) .
• 4,485
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 http://fmv.jku.at/aiger/, which will give you a circuit but ...
• 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 ...
• 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 ...
• 176

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