14

It is worth noting that the problem becomes NP-hard when the restriction is relaxed slightly. With a fixed number of clauses that are also of bounded size, the average number of literals in a clause is as close to 2 as one wants, by considering an instance with enough variables. As you point out, there is then a simple upper bound which is polynomial if ...


13

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have $\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \...


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$ ...


12

Timon Hertli, "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General", FOCS 2011. deterministic $O(1.308^n)$ for 3SAT.


11

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$. Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ ...


11

The best algorithm for 3-SAT now has numerical upper bound $O^{*}(1.306995^n)$ on unique-3-SAT and on general-3-SAT it is also fastest but now the specific values have not been analyzed yet. Authors say they hope the improved bounds for unique-3-SAT also apply directly to 3-SAT by using essentially the arguments of Hertli. The algorithm is described in ...


11

One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.


11

First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00 where there is no max. (The sup may not be attained.) Second, by "FSM" I assume you mean finite automaton. Then I claim that either the maximum bit density is achieved by a word of length < n, the number of states, or it is ...


9

I you’re looking for natural problems, you can compute many counting problems on planar graphs in time $\exp(\sqrt n)$ because of the planar separator theorem. For example, everything that can be expressed as a valuation of the Tutte polynomial [1]. Most of these problems remain #P-hard restricted to planar graphs, see Tutte Polynomial @ Wikipedia. [1] K. ...


9

Depth 2 circuits require exponential size to compute addition since a depth 2 circuit must be either DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms. Warning: the part below is buggy. See the comments under the answer. The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits ...


8

Ok, I got it. The answer is no. This can be solved in poly-time. For each 3-or-more-term clause, select a literal and set it to be true. Then solve the remaining 2-sat problem. If any one provides a solution, then that is a solution to the overall problem. Since the number of 3-or-more-term clauses is fixed (say c), then if all such clauses have size &...


7

You can use the usual switching lemma argument. You haven't explained how you represent your input in binary, but under any reasonable encoding, the following function is AC$^0$-equivalent to your function: $$ f(x_1,\ldots,x_n) = \begin{cases} 0 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 0, \\ 1 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - ...


7

I do not think this is in AC0 and I can show a lower bound for the related promise problem of distinguishing between $\sum x_i = 0$ and $\sum x_i = 2$, when $x \in \{-1, 1\}^n$. Similar Fourier techniques should apply to your problem, but I have not verified that. Or maybe there is a simple reduction. Suppose there is a size $s$ depth $d$ circuit that ...


7

This is a partial (affirmative) answer in the case when we have an upper bound on the number of zeros in every row or in every column. A rectangle is a boolean matrix consisting of one all-1 submatrix and having zeros elsewhere. An OR-rank $rk(A)$ of a boolean matrix is the smallest number $r$ of rectangles such that $A$ can be written as a (componentwise) ...


6

It's of the order 2^{0.30897m}, see http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html (I am not aware of improvements for the number of clauses.)


5

Here is some information on random instances of subset sum. This should give you a starting point at least. The main factor influencing the computational difficulty of solving (random instances of) subset sum is the relationship between the number of available terms, $n$, and the terms' size, $M$. (This is different than the 'possible combinations' idea you ...


5

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.


5

(Note: This answer works for most any consistient theory, not just $ZFC$.) We will define a machine $p$ based on the universal algorithm. $p$ does a search, looking for a string that represents a proof of a statement of the form "not ($p$ halts and outputs $n$)" (note that this requires quining, since it is self-referential), for some numeral $n$, such that ...


4

The best deterministic algorithm for 3-SAT now has upper bound 1.32793^n, see https://arxiv.org/abs/1804.07901 by Sixue Liu. Basically the upper bounds for all k-SAT have been improved in this paper.


4

Mihai Pătraşcu explained on his blog how to strengthen the variance bound of Chebyshev by looking at higher moments. He references "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al. You also might be interested in "Concentration of Measure for the Analysis of Randomized Algorithms" by Dubhashi and Panconesi.


4

Check out Lemma 4.4 in HesseAllenderBarrington - it may not be terribly useful for sequential complexity but says essentially that CRR (Chinese Remainder Representation) basis extension can be done in very uniform $\mathsf{TC}^0$. The exact bound is $\mathsf{FOM + POW} = \mathsf{FOM}$ (see also Corollary 6.2 of the same paper).


4

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, I would think it is easier to go directly for it than consider any given $X_{[k]}$. Let $X_S=\sum_{i\in S} X_i$ for a subset $S\subseteq [n]$ and $Y_k=\sum_{i=...


3

Consider $p=2q$, $q\ge 1$. Asymptotically, the quantity you are after is $2^{4q-2}$. First, let's prove a lemma of general interest. Lemma $(2^{2q}/\sqrt{\pi q})/1.136 < \binom{2q}{q} < 2^{2q}/\sqrt{\pi q}$. Proof: Recall the Robbins bounds $$ n! = \sqrt{2\pi}n^{n+1/2}e^{-n}e^{r_n}, $$ where $1/(12n+1) < r_n < 1/(12n)$. This gives $$ \binom{...


3

I don't know whether your result -- if valid -- would be a non-trivial advance, but here is one sort of problem you could test it on: Problem. Fix a function $f:\{0,1\}^n \to \{0,1\}^n$. Given $y \in \{0,1\}^n$, find $x \in \{0,1\}^n$ such that $f(x)=y$. If $f$ can be computed efficiently (say, by a small circuit), your result implies some sort of ...


3

This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see the paper "On the optimum of Delsarte's linear program" by Samorodnitsky (1998). Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$. Even for $q=2$, this is a complicated analysis, so I don'...


3

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. ...


3

The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset of transactions. Considering $D$ as an $n$ by $m$ matrix of $0$ or $1$ such that each cell indicates whether item $i$ is part of the $j$-th transaction of $D$, ...


3

The supremum bit density will either be achieved by a finite word $v$ in the language, or by the limiting bit density of some sequence $u v w, u v^2 w, u v^3 w, \ldots$ of words in the language, which equals the bit density of $v$. In both cases, we have that $|v| \leq n$ without loss of generality, where $n$ is the number of states in the finite automaton. ...


3

Let $\ell$ be the length of the longest common substring. The number of longest common substrings $m$ is at most $$ m \leq \min(k^\ell,n-\ell+1). $$ Let $x = \log_k n$. If $\ell \leq x-1$ then $m \leq n/k$. Otherwise, $m \leq n-\log_k n+2$. One checks that the latter bound is always worse, and so $m \leq n-\log_k n+2$.


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