All Questions

Filter by
Sorted by
Tagged with
3
votes
0answers
94 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 ...
7
votes
1answer
133 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 ...
3
votes
1answer
149 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 ...
3
votes
0answers
104 views

Improving boolean circuits w.r.t. a probability distribution

This is a reference request. Consider the following problem on boolean circuits [ 1 ]: Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$. Task: Find one or more ...
3
votes
1answer
225 views

Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-...
6
votes
0answers
141 views

Has what I am calling "helpfulness" here been studied?

We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
7
votes
0answers
141 views

Are there generalizations for Chow's theorem?

The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients. Are there other circuits for which ...
2
votes
1answer
89 views

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

This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636 So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
4
votes
0answers
84 views

About Boolean functions with a high sign-rank

Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
1
vote
0answers
92 views

Tribes function vs (modified) polynomial threshold circuits

Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ ...
4
votes
0answers
118 views

Looking for an exposition of the proof of the LMN theorem

Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem? The exposition of that in Ryan O'Donnel's book seems to use terminology and notation ...
7
votes
0answers
119 views

Learning function with a few low-order Fourier coefficients, from uniformly random samples

Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each ...
10
votes
1answer
342 views

Evaluate boolean circuit on batch of similar inputs

Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2. Let $x \in \{0,...
8
votes
1answer
488 views

Circuity complexity: monotone circuit of Majority function

As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+...
4
votes
0answers
468 views

Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
5
votes
1answer
388 views

Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
3
votes
1answer
141 views

Symbolic Execution of the Quine-McCluskey Algorithim

If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function. Has there been any attempts to (for lack of a better term) symbolically ...
12
votes
0answers
281 views

Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$...
6
votes
1answer
619 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the most ...
9
votes
1answer
300 views

Random restrictions and the connection to total influence of Boolean functions

Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ ...
4
votes
0answers
125 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 ...
13
votes
3answers
4k views

Circuit complexity of Majority function

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
17
votes
1answer
3k 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)$ ...
6
votes
3answers
2k views

Are Boolean circuits 'universal'

I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me. I would like to know if ...
13
votes
1answer
494 views

Hardness of noisy Boolean functions

Let $f$ be a Boolean function of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\...
15
votes
1answer
527 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 ...
3
votes
1answer
247 views

Succinct Representation and Communication complexity

Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$...
3
votes
0answers
179 views

Natural Proofs and methods for polylog depth circuit lower bounds

I have a question about the following question and its answer. Status on circuit lower bounds for polylog-bounded depth circuits In the above question, it is asked about methods to prove lower bounds ...
19
votes
2answers
937 views

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
14
votes
1answer
519 views

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability. ...
14
votes
2answers
454 views

Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma. Can we develop a Switching Lemma result to prove a size lower-bound ...
3
votes
2answers
534 views

Boolean Circuit in a Black Box?

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here. Let's equip a normal Turing machine with a "black box ...
4
votes
1answer
191 views

Computing every boolean function with a polynomial over $\mathbb{F}_3$?

The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\...
4
votes
0answers
188 views

How to prove deg(f) = n iff the parity imbalance of f is non-zero?

Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$. Here $f$ is a boolean function ...
23
votes
4answers
1k views

Monotone arithmetic circuits

The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
33
votes
2answers
1k views

Cohomological approach to boolean complexity

A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
6
votes
0answers
171 views

Distributions over circuits and N-to-N vs N-to-1 circuits

This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
29
votes
1answer
2k views

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
15
votes
1answer
851 views

Random monotone function

In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...