# Tag Info

16

If what you are studying worked out, it definitely would not be trivial. It would imply that 3SAT has (non-uniform) circuits of size $n^{O(\log n)}$. Then, every language in $NP$ (and the polynomial time hierarchy) would have quasi-polynomial (i.e., $n^{O(\log^c n)}$) size circuits. Even if it took $2^{2^n}$ preprocessing time to produce a data structure ...

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

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

11

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

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

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.

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

3

If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges. $I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any graph with a matching of size $3$ has at most $3^3\times 2^{n-6}$ independent sets, then show that we can not have two node disjoint paths of length $3$ and no ...

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