419 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Massachusetts Institute of TechnologyUS181 papers
- Vilnius UniversityLT180 papers
- Boğaziçi UniversityTR178 papers
- Deutsches Elektronen-Synchrotron DESYDE178 papers
- University of Nebraska–LincolnUS178 papers
- Bulgarian Academy of SciencesBG176 papers
- Sofia University "St. Kliment Ohridski"BG175 papers
- University of BristolGB175 papers
- University of HelsinkiFI175 papers
- University of AntwerpBE174 papers
- University of BelgradeRS174 papers
- University of Notre DameUS174 papers
6 papers · 2 filters
Proving the power of postselection
Abuzer Yakaryilmaz, A. C. Cem Say
It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time…
New separation between and
Andris Ambainis, Xiaoming Sun
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: .
Tight bounds for the space complexity of nonregular language recognition by real-time machines
Abuzer Yakaryilmaz, A. C. Cem Say
We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternatin…
Quantum counter automata
A. C. Cem Say, Abuzer Yakaryilmaz
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirma…
Finite state verifiers with constant randomness
Cem Say, Abuzer Yakaryilmaz
We give a new characterization of as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state m…
Superiority of exact quantum automata for promise problems
Andris Ambainis, Abuzer Yakaryilmaz
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in…