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 ...
Thomas's user avatar
  • 2,803
14 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 ...
Bubble's user avatar
  • 490
10 votes

What's the expressive power of Simply Typed Lambda calculus?

As explained by Damiano Mazza here on MathOverflow (see also this TCS.SE question), for a very natural choice of encodings of input strings and output booleans, one gets exactly the regular languages! ...
Lê Thành Dũng Nguyễn's 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 ...
Stasys's user avatar
  • 6,765
7 votes

Solving 3-SAT in O(n^6)?

You can find all weird stuff out there... For example, just google "graph isomorphism problem 2022", and the first search result is this polytime algorithm... https://www.biorxiv.org/content/...
Avi Tal's user avatar
  • 1,606
7 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 ...
Neal Young's user avatar
7 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 ...
Lieuwe Vinkhuijzen's user avatar
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, ...
Jason Gaitonde's 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 ...
Christopher King's 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.
ON KI Wong's user avatar
3 votes
Accepted

Confusion about lower bounds and upper bounds in learning theory

I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed. To elaborate on Usul's comment. Upper bounds are of the ...
Aryeh's user avatar
  • 10.5k
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}} = \...
mathworker21's user avatar
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 ...
Soumya Basu's 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 ...
Meni's 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. ...
Alexander S. Kulikov's 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}$. ...
Highheath's user avatar
  • 211
1 vote

Upper Bound for distance-two chromatic number in terms of maximum degree

Let $\Delta$ denote the maximum degree of $G$. The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
Cyriac Antony's user avatar
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. ...
Stella Biderman's 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{|...
Luz's 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 \...
Igor Shinkar's user avatar
  • 1,917

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