Questions tagged [upper-bounds]
The upper-bounds tag has no usage guidance.
71
questions
51
votes
9
answers
12k
views
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
- 16.6k
42
votes
3
answers
2k
views
A fixed-depth characterization of $TC^0$? $NC^1$?
This is a question about circuit complexity. (Definitions are at the bottom.)
Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{...
- 27.5k
24
votes
1
answer
2k
views
What's the expressive power of Simply Typed Lambda calculus?
The standard approach to simply typed lambda calculus considers computations over Church numerals.
If input and outputs are Church numerals always typed as $Int$, where $Int = (\tau \rightarrow \tau) ...
- 401
21
votes
2
answers
1k
views
Can addition be carried out in less than depth 5?
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
- 4,041
19
votes
1
answer
2k
views
What are the limits of computation in this universe?
I understand that Turing completeness requires unbounded memory and unbounded time.
However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$...
- 393
15
votes
2
answers
1k
views
How large a treewidth can a tree plus half the edges have?
Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?
It ...
- 1,404
14
votes
2
answers
530
views
OR-circuit complexity of a dense linear operator
Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
14
votes
0
answers
210
views
The best known upper bound for two-way probabilistic finite automata with one-counter
It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $ \mathsf{L} $ (deterministic log-space):
A 2D1CA can run at ...
- 3,707
13
votes
2
answers
969
views
What is the proof of this nonstandard version of Azuma's inequality?
In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:
Let $C_1, \dots, C_k$ be real-valued ...
- 1,753
12
votes
0
answers
648
views
Known upper bounds on the communication complexity of Karchmer-Wigderson games
In 1988 Karchmer and Wigderson established a nice characterization of the circuit
depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number ...
- 2,247
11
votes
2
answers
841
views
Are quasi-polynomial sized circuits for 3-SAT trivial?
Suppose we consider 3-SAT with $v$ variables and $c$ clauses. I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within ...
- 2,110
11
votes
1
answer
1k
views
What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?
I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
- 2,628
10
votes
2
answers
2k
views
Is Almost-2-SAT NP-hard?
Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant? What about specifically when there's only one such clause?
- 916
9
votes
2
answers
230
views
Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$
Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = ...
- 2,327
8
votes
1
answer
1k
views
Probability of two vertices being connected by some path in a random directed graph
Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$).
What are the known results for the following problem:
Fix two vertices $v$ and $u$...
- 749
8
votes
0
answers
366
views
Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$
An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean ...
- 143
7
votes
4
answers
1k
views
What are the best known upper bounds and lower bounds for computing O(log n)-Clique?
Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great
- 21.1k
7
votes
2
answers
460
views
What are the current best upper bounds of #P?
#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP.
I'm wondering if there have been any studies ...
- 2,110
7
votes
2
answers
518
views
What bound can we get using $k$-th moment inequality under 3-wise independence?
Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)...
- 201
7
votes
2
answers
305
views
Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?
For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$:
$$S=C_1 \wedge \ldots \wedge C_T$$
where a non-degenerate clause is one containing $3$ unique ...
- 181
7
votes
1
answer
113
views
How quickly can we perform base extension in a residue number system?
Thinking about residue number systems, one major operation is to extend the set of primes that a given value is modulated by, also known as base extension. For instance, a given number $N$ can be ...
- 2,110
7
votes
0
answers
157
views
What's the upper bounds for #3-SAT circuits?
We have, from this thread on 3-SAT upper bounds, and this answer on #P that the current best upper bounds for 3-SAT is faster than $O(1.31)^n$, and approximately $O(1.64^n)$ for #3-SAT.
Can we do ...
- 2,110
6
votes
2
answers
2k
views
Number of edges in $K_4$-free graphs
What can be the upper bound on the number of edges in a graph of $n$ vertices such that the graph does not have $K_4$ as a minor? Is there some relevant paper/book that I can look into it or it would ...
- 725
6
votes
1
answer
407
views
Big-O bounds on the k-th largest element of iid Gaussians
I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \...
- 233
6
votes
1
answer
326
views
Best SAT upper bounds based on number of clauses
What's the best upper bounds based on number of clauses? In this question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of ...
6
votes
1
answer
457
views
Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?
Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal ...
- 481
6
votes
1
answer
261
views
Best upper bound on rate for q-ary codes
Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation ...
- 61
6
votes
1
answer
191
views
Bounds on the size of NFA for $r$-skip $k$-distinct language
This question is about an extension of a language discussed in this question.
We define the $r$-skip $k$-distinct language as follows:
$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \...
- 9,488
5
votes
2
answers
466
views
Bit complexity of integer factorization?
Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer ...
- 21.1k
5
votes
1
answer
507
views
What is the running time of taking a limit?
I'm interested in finding the running time(s) for determining mathematical limits.
For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.
I'd like to know more about algorithms for determining ...
- 2,110
5
votes
1
answer
242
views
Upper bound on the expected number of correct bits via a "lossy compression"
Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
5
votes
0
answers
373
views
Strongly edge-guarding a 3d triangulation
Let $T$ be a planar triangulation. It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and ...
user183
4
votes
0
answers
114
views
Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$
Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience.
So, Iet $X = (X,d)$ be a Polish space, ...
- 291
4
votes
0
answers
130
views
Deciding transitivity of a directed acyclic graph [duplicate]
Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
- 399
3
votes
2
answers
249
views
computing maximal bit density over a FSM
let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("...
- 11.1k
3
votes
1
answer
764
views
Subset Sum bounds
Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
- 173
3
votes
1
answer
158
views
Number of different longest common substrings
Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
- 500
3
votes
1
answer
189
views
Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$
I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.
Given $p$, I am looking for a ...
- 1,542
3
votes
0
answers
29
views
Bound on line with minimum zone complexity in a line arrangement
In an arrangement of $n$ (pseudo)lines, the well known Zone Theorem gives a $O(n)$ bound on the complexity of the zone of any given line (for the purpose of this question, the complexity of the zone ...
- 881
3
votes
0
answers
223
views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
- 2,110
3
votes
1
answer
122
views
Is there an established name for this kind of upper bound?
Assume for some algorithmic problem it holds that, for each $\epsilon>0$, there is some algorithm that needs space at most $O(n^\epsilon)$.
Is there an established name for this kind of bound?
I'd ...
- 1,417
2
votes
1
answer
115
views
Upper bound to number of closed itemsets
Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper ...
- 569
2
votes
1
answer
160
views
Is the center of a BFS tree a good approximation of the graphs center?
Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$).
Finding the center of the graph can easily be done using all-pairs-shortest-...
- 21
2
votes
1
answer
125
views
References on generalization bounds
I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or ...
- 63
2
votes
1
answer
79
views
Upper Bound for distance-two chromatic number in terms of maximum degree
Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a function $f:V(G)\to\{1,2,\dots\}$ such that $f(u)\neq f(v)$ whenever $dist_G(u,v)\leq 2$. A distance-two ...
- 1,827
2
votes
1
answer
124
views
Upper bound on the size of a Concept Lattice (Galois Lattice)?
A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ ...
- 427
2
votes
1
answer
192
views
Probability of random variable $X$ less than $max(Y_i)$
For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.
Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\...
- 791
2
votes
0
answers
128
views
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
- 225
2
votes
0
answers
1k
views
Is there a better than brute-force solution to the shortest simple path problem?
Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex ...
- 121
2
votes
0
answers
225
views
Circuit complexity lower bounds and uniformity
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.
For example, the word problem for ...
- 31