Questions tagged [upper-bounds]

The tag has no usage guidance.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20
votes
0answers
1k 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) ...
14
votes
0answers
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 ...
12
votes
0answers
611 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 ...
8
votes
0answers
348 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 ...
7
votes
0answers
148 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 ...
5
votes
0answers
370 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 ...
4
votes
0answers
82 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, ...
3
votes
0answers
160 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
votes
0answers
80 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 ...
2
votes
0answers
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 ...
2
votes
0answers
196 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 ...
2
votes
0answers
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 ...
2
votes
0answers
114 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 ...
1
vote
0answers
43 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 ...
1
vote
0answers
66 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,...
1
vote
0answers
300 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 ...
1
vote
0answers
855 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(...
1
vote
0answers
383 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, ...
1
vote
0answers
207 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). ...
0
votes
0answers
37 views

Expected value in case of Langevin dynamics

Let $U(\beta) = \exp(-f(\beta))$ where $f$ is $m$ strongly convex and $L$ Lipschitz smooth. I am trying to find an upper bound on $E[\|\beta_t \|^2]$ where $\beta_t \in \mathcal{R}^p$ is defined below ...
0
votes
0answers
33 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
1answer
129 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). ...