Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > STABILITY:
Reports tagged with stability:
TR95-025 | 8th May 1995
Günter Hotz, Gero Vierke, Bjoern Schieffer

Analytic Machines

Comments: 1

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 >>>


TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

Stable basis families and complexity lower bounds

--
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 >>>


TR03-016 | 15th January 2003
Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

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 >>>


TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

Are stable instances easy?

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 >>>


TR24-064 | 1st April 2024
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

No Complete Problem for Constant-Cost Randomized Communication

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 >>>




ISSN 1433-8092 | Imprint