88 citations
- University of AmsterdamNL11 papers
- College of Western IdahoUS3 papers
- Vrije Universiteit AmsterdamNL3 papers
- Universidad Pública de Navarra (UPNA)ES2 papers
- University of CambridgeGB2 papers
- University of TwenteNL2 papers
- Berkeley CollegeUS1 paper
- Eindhoven University of TechnologyNL1 paper
- Goethe University FrankfurtDE1 paper
- Institute for Advanced StudyUS1 paper
- Laboratoire de Recherche en InformatiqueFR1 paper
- Lomonosov Moscow State UniversityRU1 paper
8 papers · 1 filter
Sojourn times in the M/G/1 FB queue with light-tailed service times
Michel Mandjes, Misja Nuyens
The asymptotic decay rate of the sojourn time of a customer in the stationary M/G/1 queue under the Foreground Background (FB) service discipline is studied. The FB discipline give…
Clustering by compression
Rudi Cilibrasi, Paul Vitanyi
We present a new method for clustering based on compression. The method doesn't use subject-specific features or background knowledge, and works as follows: First, we determine a u…
The minimal spanning tree and the upper box dimension
Gady Kozma, Zvi Lotker, Gideon Stupp
We show that the alpha-weight of an MST over n points in a metric space with upper box dimension d has a bound independent of n if alpha is smaller than d and does not have one if…
Robust Polynomials and Quantum Algorithms
Harry Buhrman, Ilan Newman, Hein Roehrig +1
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We co…
Quantum Symmetrically-Private Information Retrieval
Iordanis Kerenidis, Ronald de Wolf
Private information retrieval systems (PIRs) allow a user to extract an item from a database that is replicated over k>=1 servers, while satisfying various privacy constraints. We…
Individual Communication Complexity
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin +1
We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correc…