# Questions tagged [upper-bounds]

The tag has no usage guidance.

60 questions
Filter by
Sorted by
Tagged with
24 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, ....
76 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, ...
211 views

97 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 ...
41 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 ...
104 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 ...
134 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 ...
70 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 ...
475 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 ...
587 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?...
364 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 ...
790 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 ...
972 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 ...
109 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$ ...
160 views

103 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 ...
111 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 ...
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?
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 ...
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,... 1answer 619 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 ... 1answer 127 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). ... 0answers 279 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 ... 2answers 966 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? 2answers 224 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 = ... 0answers 708 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(... 2answers 406 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 ... 1answer 167 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 ... 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 ... 2answers 390 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)... 1answer 102 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 ... 1answer 214 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 ... 0answers 366 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 ... 2answers 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 ... 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) ... 0answers 207 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 ... 2answers 754 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 ... 0answers 596 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 ... 1answer 601 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 n}(x_i-\alpha)^{...
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, ...