Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [upper-bounds]

The tag has no usage guidance.

71 questions
Filter by
Sorted by
Tagged with
1 vote
123 views

### Upper bound on the number of maximal paths in rooted intransitive DAGs

Let $D(V, A)$ be a DAG. Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path. Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs ...
124 views

### Confusion about lower bounds and upper bounds in learning theory

In computer science, lower bounds and upper bounds are defined as follow: $$m \geq g(n) \implies m = \Omega(g(n))$$ $$m \leq g(n) \implies m = \mathcal{O}(g(n))$$ However, in proving lower bounds and ...
• 65
120 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
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
641 views

### Solving 3-SAT in O(n^6)?

There's an algorithm (published on GitHub) which is claimed to solve any 3-SAT formulation in polynomial time with a complexity of max O(n^6). I would usually brush claims like this away, but having ...
• 73
1 vote
105 views

### Which is the most efficient of the two following approximation algorithms?

Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps \begin{align*} \mathrm{Value} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Upper} &: \mathfrak{B}...
• 111
1 vote
50 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
154 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
72 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,733
288 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
241 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 ...
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, ....
110 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
392 views

120 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
1 vote
47 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 ...
121 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 ...
• 111
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,100
121 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
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 ...
1 vote
787 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?...
• 111
455 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 ...
962 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,743
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
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
190 views

• 9,458
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
137 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 ...
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
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 ...
• 393
1 vote
68 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
760 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
140 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 vote
340 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
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
230 views

• 111
456 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,100
188 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
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 ...