Questions tagged [upper-bound]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
1answer
43 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
87 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
110 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
42 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
65 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
0answers
103 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
41 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
50 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
43 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 ...