Questions tagged [upper-bound]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
1answer
70 views

Construct a Circuit computing all boolean functions over n bits

Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ ...
2
votes
1answer
102 views

Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
2
votes
0answers
24 views

Anagram sorting with inversion count oracle

Given a permutation $P$ of an unknown array $U$ of length $N$ and a function $f(Q)$ that calculates the minumum number of swaps between consecutive elements of array $Q$ to reach $U$, what is the ...
2
votes
0answers
127 views

Maximum value reached in extended binary GCD

Given positive integer inputs $x$ and $y$ , with $0<x<y$ and $y$ an odd prime (or $\gcd(x,y)=1$ and $y$ odd), the following algorithm computes $x^{-1}\bmod y$ per the (half-)extended binary GCD. ...
2
votes
0answers
45 views

What's the reason for sqrt(n) bounds in online learning?

I have a question regarding no-regret algorithms (of online learning). As far as I can see, such algorithms allow the absolute regret up to round $n$, which is $R_n$, to grow by $\sqrt{n}$. So, in the ...
2
votes
0answers
69 views

What is the largest number of Byzantine failures that can be tolerated in an $m$-dimensional hypercube for the consensus problem?

We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that ...
1
vote
1answer
26 views

Complexity of two-party maximum

Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$),...
1
vote
0answers
120 views

Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs

Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
0
votes
0answers
10 views

Why the proof of the hyperbolic bound for rate-monotonic scheduling works?

Recently I'm trying to prove the hyperbolic bound for rate-monotonic scheduling (RMS). [original paper] http://retis.sssup.it/~giorgio/paps/2001/ecrts01-hb.pdf [more formal paper] https://ieeexplore....
0
votes
0answers
11 views

Does regret change when the loss function is dependent on the previous predictions?

The loss function of each expert in the expert advice problem(or any online learning problem) depends on the time($t$) and expert advice at that time($f_{t}(i)$). suppose in this problem, loss ...
0
votes
0answers
19 views

Bounding 0-1 matrix with k unique rows

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
0
votes
0answers
43 views

Perceptron : upper bound

Given the following theorem: $\textbf{Theorem (Perceptron)}:$ Let $S$ be a sequence of labeled examples consistent with a linear threshold function $w^T \cdot x > 0,$ where $w$ is a unit-length ...
0
votes
1answer
60 views

Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...
0
votes
0answers
44 views

Correctness of algorithm and its complexity

I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph. So, I found this paper proposing an ...