15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

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 ...
user avatar
  • 2,743
12 votes
Accepted

Best Upper Bounds on SAT

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 ...
user avatar
  • 470
11 votes
Accepted

computing maximal bit density over a FSM

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 ...
user avatar
7 votes
Accepted

OR-circuit complexity of a dense linear operator

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 ...
user avatar
  • 6,615
6 votes
Accepted

Best SAT upper bounds based on number of clauses

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.)
user avatar
  • 250
6 votes

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

Theorem 1. For all $n\ge 6$ and $T$ with $n+14\le T \le 7{n\choose 3}$, there is a satisfiable 3-SAT formula on $n$ variables with $T$ clauses in which all clauses are redundant. Before we give the ...
user avatar
  • 8,223
6 votes
Accepted

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

I interpret the question as: given $n$ and $T$, what is the maximum number of redundant clauses a satisfiable $n$-variable formula on $T$ clauses can have? For the purposes of this question, I find it ...
user avatar
5 votes
Accepted

Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?

(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 ...
user avatar
  • 471
5 votes
Accepted

Big-O bounds on the k-th largest element of iid Gaussians

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, ...
user avatar
5 votes
Accepted

Upper bound for number of independent sets

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.
user avatar
4 votes

Best Upper Bounds on SAT

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.
user avatar
3 votes
Accepted

Upper bound on the expected number of correct bits via a "lossy compression"

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}} = \...
user avatar
3 votes
Accepted

Probability of two vertices being connected by some path in a random directed graph

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 ...
user avatar
  • 14.1k
3 votes

Upper bound to number of closed itemsets

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 ...
user avatar
3 votes

computing maximal bit density over a FSM

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 ...
user avatar
3 votes
Accepted

Number of different longest common substrings

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 ...
user avatar
  • 14.1k
3 votes

Upper bound for number of independent sets

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 ...
user avatar
2 votes

Bounds on the size of NFA for $r$-skip $k$-distinct language

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 ...
user avatar
  • 7,653
2 votes

How is additive error handled in this simple algorithm? 'Product of all elements'

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 ...
user avatar
2 votes
Accepted

References on generalization bounds

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 ...
user avatar
  • 168
2 votes

OR-circuit complexity of a dense linear operator

(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. ...
user avatar
2 votes

Is the center of a BFS tree a good approximation of the graphs center?

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound). Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
user avatar
  • 211
1 vote

Common terminology used for lower/upper bounds

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. ...
user avatar
1 vote
Accepted

Upper bound on the size of a Concept Lattice (Galois Lattice)?

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{|...
user avatar
  • 427
1 vote

Probability of random variable $X$ less than $max(Y_i)$

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 \...
user avatar
  • 1,897

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