15

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}] \...


15

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


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.


12

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

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


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

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

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


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


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

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


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.


3

Let $f(n,s)$ denote the answer. Claim: We have $f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$ for any fixed $s$ as $n \to \infty$. More precisely, $\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \Theta(\sqrt{s})$ for $s \ge 1$. Proof: For the lower bound, have the compressor divide into $s$ (nearly) equal pieces and output the (string of length $s$ ...


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


2

I detail the comment below, as you could be interested in this answer. I don't know about NFA, but if your goal is to represent this language with a small automaton, you could use the model of alternating automata, or AFA. Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA ...


2

Use Taylor series expansion for the function $\prod_{i=1}^{n} (u_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$. Note that Taylor series works for $\epsilon = O(1/poly(n))$, because $\mathbf{u}$ is a unit normed vector and the product $\prod_{j=1}^{n} u_j < 1$.


2

For a concise overview the ideas you can read Mendelson's notes on the topic. For a bit more check out the outline (and the links in it) by Kontorovich on how the basic and most fundamental bonds where proved. For a more extended discussinon you can go over lecture notes of statistical learning courses. Here is one for example. If books are your ...


2

(I tried to post this as a comment to Stasys' answer above, but this text is too long for a comment, so posting it as an answer.) Ivan Mihajlin (@ivmihajlin) came up with the following construction. Similarly to Stasys' proof, it works for the case when the maximum (rather than average) number of 0’s in each row is bounded. First, consider the case when ...


1

The term “tight” has multiple uses, as is mentioned in a comment. However, you seem to be interested in a combinatorial context or on a combinatorial-type problem so I’m going to assume that contexts. Let’s say we are talking about a function, $f(n)$, that bounds $g(n)$. In your case, $g$ is the true number of vertices of the $n^{th}$ graph in your family ...


1

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$


1

We have $\Pr[\max(Y_1,Y_2) \leq k] = \Pr[Pois(\lambda) \leq k]^2 = e^{-2\lambda}(\sum_{j=0}^k\frac{\lambda^j}{j!})^2$. Therefore, $\Pr[X \geq \max(Y_1,Y_2)] = \sum_{k \in \mathbb N} \Pr[X = k] \cdot \Pr[\max(Y_1,Y_2) \leq k] = e^{-(2\lambda+\mu)} \bigg (\sum_{k = 0}^\infty\frac{\mu^k}{k!} \cdot (\sum_{j=0}^k \frac{\lambda^j}{j!})^2 \bigg)$. From this, if ...


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