We’re rewarding the question askers & reputations are being recalculated! Read more.
32

Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the ...


30

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials. Claim: The polynomials $\{ \prod_{i \in S} x_i : ...


26

Let $p$ be a polynomial such that for all $x\in \{0,1\}^n$, $p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial $p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that, since the OR function is a symmetric boolean function, we have that for $k = 1, 2, \ldots, n$, $q(k) = 1$, and $q(0) = 0$. Since $q-1$ is a non-zero ...


21

Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the GLL blog. More precisely: Theorem: Suppose $f : \{0,1\}^n \to \{0,1\}^m$ is computed by a circuit $C$ with $g$ gates, then it is also computed ...


19

Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random. To Sasho Nikolov, this is a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish ...


19

A family of bitvectors is the class of solutions to a 2-SAT problem if and only if it has the median property: if you apply the bitwise majority function to any three solutions you get another solution. See e.g. https://en.wikipedia.org/wiki/Median_graph#2-satisfiability and its references. So if you can find three solutions for which this is not true, then ...


18

Ben-Or directly proved $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model: Element distinctness: Given an array of $n$ real numbers, are its elements distinct? Set disjointness: Given two sets of $n$ real numbers, do they have an element in common? Set equality: Given two sets of $n$ real numbers, is one ...


18

According to the paper A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function by Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and ...


17

This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (http://eccc.hpi-web.de/report/2013/169/). As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula. Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can ...


16

Let $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$. The problem is to determine whether the following system has a solution: $$ \begin{pmatrix} v_1 & \cdots & v_n \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = v_0 \, (\text{mod } 2) $$ This problem is known to be $\oplus L$-complete by [Damm90, BDHM92], thus inside $\text{...


16

In a recent paper, Braverman, Garg, Pankratov, and Weinstein compute the value of $\delta$ to be exactly some constant around 0.4827, up to sublinear factors. This gives a tight bound on the communication complexity of disjointness. The constant itself was found using a computer algebra system, and as far as I'm aware can't be expressed simply.


16

On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under restricted settings. Like, in the work leading to GCT that you mention, the lower bound applies to a restricted PRAM model without bit operations. Under another restriction, which is the monotone restriction for monotone boolean functions, there is a Fourier-...


15

An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see Holger Dell, Thore Husfeldt, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/ That is, if ...


15

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order. It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you ...


15

There are "natural" problems hard for Ackermannian time; in fact there is a growing body of literature on the subject. A place to start is the survey in Section 6 of Complexity Hierarchies Beyond Elementary. What is even more interesting is that there are complete problems for Ackermannian time, under say primitive-recursive many-one reductions: define for ...


14

This paper of Blum & Seysen may be useful: N.Blum, M. Seysen. Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR. Acta Inf. 21: 171-181 (1984) I have thought that for $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$ lower bound can be obtained using methods of Blum & Seysen, but it seems this is not the case.


14

Following the suggestion of Kaveh, I am putting my comment as an (expanded) answer. Concerning $Q1$, a word of caution is in order: even logarithmic depth if far from being understood, not speaking about poly-logarithmic. So, in the non-monotone world, the real problem is much less ambitious: Beating Log-depth Problem: Prove a super-linear(!) lower bound ...


14

Hmm, turns out there's actually an matching upper bound that isn't too hard: To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of machines of description length at most $n$ which halt. This number is not more than $2^{n}$, so it can be represented with about $n$ bits. Then we can start all such ...


13

According to Theorem 3.1 in Alexis Maciel and Denis Therien Threshold Circuits of Small Majority-Depth there is indeed a depth-3 circuit for computing the addition of two numbers. The precise bound is $\Delta_2 \cdot \mathsf{NC}^0_1$ where $\Delta_2 = \Sigma_2 \cap \Pi_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ ...


13

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over some field. Their model of computation is the straight-line programs: The goal is to compute $n!$ from the constant $1$, using only additions, subtractions and ...


13

The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$ in an outdegree one graph $G$, that is promised to be a path) is $\mathsf{L}$-hard under quantifier free projections. The problem $\mathbf{ORD}$ can be seen ...


12

I'd suggest looking at properties of #P functions that are different than Gap-P functions. For example, determining if a #P function is zero is in co-NP. If you could show determining whether the Kronecker coefficients is zero is UP-hard then you would have "Kronecker coefficients in #P implies UP in co-NP", an unlikely conclusion.


12

The bounds... We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper. ...cannot be substantially improved There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof ...


11

As a followup to my comment: finding the smallest satisfying subset should in fact be NP-complete; the reduction is to the minimal-weight code problem (given a basis for a code over GF(2), what's the minimum-weight vector in the code?) and this was apparently proven NP-complete in 1997 by A. Vardy: "The intractability of computing the minimum distance of a ...


11

Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time. There is a whole paper developing such hardness results using something called the "representation problem". To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak ...


11

It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits. In particular in the paper Size-Depth Tradeoffs for Threshold Circuits, Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function. ...


11

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open. In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $...


11

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On ...


11

The result can be found in Beigel, R., Gasarch, W. I., Gill, J., and Owings, J. Terse, superterse, and verbose sets. Inform. and Comput. 103 (1993), no. 1, 68–85. Their proof in fact shows that your problem cannot be solved with fewer than $\log_2 n$ queries to any set $X$, let alone to the halting problem itself. For some notation, your problem is ...


11

here are new results on this said to be the 1st in ~3 decades and some brief commentary A better-than-3n lower bound for the circuit complexity of an explicit function / Find, Golovnev, Hirsch, Kulikov We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n−o(n)$ lower bound on the size of such a circuit for an explicitly ...


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