Questions tagged [upper-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
114 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-...
user avatar
  • 21
1 vote
0 answers
23 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 ...
user avatar
6 votes
2 answers
187 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 ...
user avatar
  • 171
0 votes
0 answers
37 views

Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
user avatar
  • 101
5 votes
1 answer
204 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 ...
user avatar
0 votes
0 answers
39 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, ....
user avatar
4 votes
0 answers
89 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, ...
user avatar
  • 217
6 votes
1 answer
287 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]} = \...
user avatar
-1 votes
1 answer
78 views

How is additive error handled in this simple algorithm? 'Product of all elements'

Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u_1,...,u_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$ where $\epsilon = \...
user avatar
2 votes
1 answer
106 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 ...
user avatar
  • 63
1 vote
0 answers
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 ...
user avatar
-1 votes
1 answer
119 views

Finding upper and lower bounds of a problem [closed]

We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans ...
user avatar
  • 111
3 votes
0 answers
173 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 ...
user avatar
  • 2,080
2 votes
0 answers
98 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 ...
user avatar
14 votes
2 answers
525 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 ...
user avatar
1 vote
1 answer
708 views

Common terminology used for lower/upper bounds

Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
user avatar
  • 111
6 votes
1 answer
418 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 ...
user avatar
  • 471
13 votes
2 answers
884 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 ...
user avatar
  • 1,733
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 ...
user avatar
  • 121
2 votes
1 answer
119 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$ ...
user avatar
  • 427
2 votes
1 answer
166 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\...
user avatar
8 votes
0 answers
354 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 ...
user avatar
2 votes
0 answers
200 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 ...
user avatar
  • 31
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$...
user avatar
  • 739
6 votes
1 answer
256 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 ...
user avatar
3 votes
2 answers
246 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 ("...
user avatar
  • 10.8k
7 votes
0 answers
150 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 ...
user avatar
  • 2,080
3 votes
1 answer
147 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 ...
user avatar
  • 490
1 vote
2 answers
719 views

Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
user avatar
  • 155
6 votes
1 answer
181 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} | \...
user avatar
  • 9,378
2 votes
1 answer
113 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 ...
user avatar
  • 569
0 votes
1 answer
130 views

Number of $k$-cuts of grid graphs

Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$. Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on ...
user avatar
4 votes
0 answers
126 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?
user avatar
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 ...
user avatar
  • 383
1 vote
0 answers
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,...
user avatar
  • 13
3 votes
1 answer
734 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 ...
user avatar
  • 173
0 votes
1 answer
133 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). ...
user avatar
  • 31
1 vote
0 answers
325 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 ...
user avatar
  • 31
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?
user avatar
  • 916
9 votes
2 answers
226 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 = ...
user avatar
  • 2,267
1 vote
0 answers
910 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(...
user avatar
7 votes
2 answers
425 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 ...
user avatar
  • 2,080
3 votes
1 answer
174 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 ...
user avatar
  • 1,502
2 votes
0 answers
120 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 ...
user avatar
  • 201
7 votes
2 answers
432 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)...
user avatar
  • 201
7 votes
1 answer
104 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 ...
user avatar
  • 2,080
6 votes
1 answer
235 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 ...
user avatar
  • 61
5 votes
0 answers
371 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 ...
user avatar
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 ...
user avatar
  • 3,993
21 votes
0 answers
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) ...
user avatar
  • 371