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 ...
- 2,793
13
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 ...
- 480
9
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! ...
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/...
- 1,566
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 ...
- 6,655
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.)
- 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 ...
- 9,555
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 ...
- 1,934
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, ...
- 800
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 ...
- 471
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.
- 41
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 ...
- 14.2k
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}} = \...
- 320
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}$. ...
- 211
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 ...
- 171
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 ...
- 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. ...
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. ...
- 1,046
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{|...
- 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 \...
- 1,897
Only top scored, non community-wiki answers of a minimum length are eligible