Questions tagged [upper-bounds]
The upper-bounds tag has no usage guidance.
25
questions with no upvoted or accepted answers
14
votes
0
answers
209
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,677
12
votes
0
answers
635
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,162
8
votes
0
answers
361
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
0
answers
151
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,080
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
96
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
3
votes
0
answers
218
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,080
3
votes
1
answer
119
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
0
answers
17
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 ...
- 351
2
votes
0
answers
112
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
210
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
2
votes
0
answers
1k
views
Maximum number of triangles in a constrained delaunay triangulation
I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number ...
- 383
2
votes
0
answers
125
views
What upper bound can we get under 3-wise independence? (comparable edition)
Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than ...
- 201
1
vote
0
answers
49
views
What is known about simultaneous protocol set disjointness?
Assume that Alice and Bob have sets $A,B\subseteq[n]$ of size $|A|=|B|=k$.
In the simultaneous protocol, they both send a message to Carol (that doesn't observe $A$ and $B$) which needs to determine ...
- 11
1
vote
0
answers
32
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 fuction $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,633
1
vote
0
answers
46
views
Optimally fair stable matching
There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively.
In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...
- 369
1
vote
0
answers
67
views
Bound the number of rounds in the sampling
Suppose we have a sequence $a_1,a_2,\ldots, a_n$, each $a_i$ is sampled uniformly and independently from $[0,1]$.
Define
$$
J_1=1,\\
\text{for}~i>1, ~J_i = 1 \iff a_i < \min \{a_1,a_2,...
- 13
1
vote
0
answers
337
views
Bin packing upper bound: total size of items = k, bin size = r
Suppose you have items, whose total size (i.e. sum of sizes) is $k$.
The number of items and their individual sizes are unknown integers.
We need to pack the items into bins of size $r$.
I need to ...
- 31
1
vote
0
answers
949
views
Are there upper bounds on the worst case complexity of NP-complete problems?
I have proven some problem to be (weakly) NP-complete and try to find out some algorithm to solve it exactly. Except for some pseudo-polynomial stuff, I would be happy with an algorithm running in $O(...
- 111
1
vote
0
answers
414
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, ...
- 749
1
vote
0
answers
208
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).
...
- 11
0
votes
0
answers
45
views
Is this a proof that diophantine equation solutions can't be bounded by power towers?
From this 2017 paper on upper bounds for solutions to diophantine equations:
Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution
in positive integers x1, . . . , xn , then x1, ....
0
votes
1
answer
135
views
Counting subsets with large sum
Suppose that you have a multiset of positive integers $I$.
$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.
(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).
...
- 31
-1
votes
0
answers
56
views
Bin packing with variable size bins
Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$ and bin capacities $b_1,\dots, b_n \geq 1$. The task is to pack the items in as a few bins as possible such ...
