The upper-bounds tag has no wiki summary.
-1
votes
0answers
30 views
Time complexity in Big O notation for Harmonic series with first k terms missing [migrated]
Firstly, let's suppose there exists an algorithm where i iterates from 1 to n, spending n^2/i time in each iteration.
Thanks to the well known O(logn) upper bound for the Harmonic series, the big O ...
-2
votes
0answers
47 views
Finding the lower bounds of an algorithm [closed]
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
7
votes
1answer
63 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 ...
3
votes
0answers
90 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 ...
5
votes
0answers
271 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 ...
17
votes
1answer
663 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 ...
6
votes
0answers
208 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) ...
12
votes
0answers
165 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 ...
9
votes
2answers
544 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 ...
11
votes
0answers
313 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 ...
-1
votes
1answer
199 views
Upper bound of an optimization problem
Please let me know whether there are closed-form optimal results (or upper bound) for the following optimization problem:
$$\max (\prod_{1\leq i\leq n}(x_i)^{y_i}-\prod_{1\leq i\leq ...
1
vote
0answers
277 views
Succinct representation of boolean functions
Let $f$ be a boolean function over $n$ variables $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}$. We are looking now for a representation of $f$ s.t. when given that representation and values $x_1, \ldots, ...
5
votes
2answers
270 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 ...
10
votes
1answer
511 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 service thus making memory bounded. For example even though ...
1
vote
0answers
162 views
Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$
Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$?
(Set cover).
...
4
votes
1answer
415 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 ...
34
votes
3answers
1k 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 ...
3
votes
1answer
239 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.
23
votes
5answers
2k 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 ...
6
votes
4answers
631 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
14
votes
2answers
448 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 ...
