Günter Hotz, Gero Vierke, Bjoern Schieffer

In this paper the $R$-machines defined by Blum, Shub and Smale

are generalized by allowing infinite convergent computations.

The description of real numbers is infinite.

Therefore, considering arithmetic operations on real numbers should

also imply infinite computations on {\em analytic machines}.

We prove that $\R$-computable functions are $\Q$-analytic.

We show ...
more >>>

Per Enflo, Meera Sitharam

--

Scalar product estimates have so far been used in

proving several unweighted threshold lower bounds.

We show that if a basis set of Boolean functions satisfies

certain weak stability conditions, then

scalar product estimates

yield lower bounds for the size of weighted thresholds

of these basis functions.

Stable ...
more >>>

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

In this work, we study the stability of the {\sf FIFO} ({\sf

First-In-First-Out}) protocol in the context of Adversarial

Queueing Theory. As an important intermediate step, we consider

{\em dynamic capacities}, where each network link capacity may

arbitrarily take on values in the two-valued set of integers

$\{1,C\}$ for $C>1$ ...
more >>>

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete

optimization problem, and argue that in many practical situations

only sufficiently stable instances are of interest. The question

then arises whether stable instances of NP--hard problems are

easier to solve. In particular, whether there exist algorithms

that solve correctly ...
more >>>

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with ... more >>>