Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Peyman Afshani:

TR13-187 | 27th December 2013
Peyman Afshani, Kevin Matulef, Bryan Wilkinson

Property Testing on Linked Lists

Revisions: 1

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

TR12-087 | 4th July 2012
Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

We study the $\leadingones$ game, a Mastermind-type guessing game first
regarded as a test case in the complexity theory of randomized search
heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a
permutation $\pi$ of $[n]$.
The goal of the second player, Paul, is to ... more >>>

ISSN 1433-8092 | Imprint