Cookies Policy
We use cookies to improve our site and your experience. By continuing to browse our site you accept our cookie policy. Find out More
Close
  • Menu
Interest
Topics
Details

Details

Publications

2018

Catalytic Space: Non-determinism and Hierarchy

Authors
Buhrman, H; Koucký, M; Loff, B; Speelman, F;

Publication
Theory Comput. Syst.

Abstract
Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation. © Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman; licensed under Creative Commons License CC-BY.

2017

Lower Bounds for Elimination via Weak Regularity

Authors
Chattopadhyay, A; Dvorák, P; Koucký, M; Loff, B; Mukhopadhyay, S;

Publication
34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany

Abstract

2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity

Authors
Brody, J; Buhrman, H; Koucký, M; Loff, B; Speelman, F; Vereshchagin, NK;

Publication
Algorithmica

Abstract

2016

Catalytic Space: Non-determinism and Hierarchy

Authors
Buhrman, H; Koucký, M; Loff, B; Speelman, F;

Publication
33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France

Abstract

2015

Hardness of Approximation for Knapsack Problems

Authors
Buhrman, H; Loff, B; Torenvliet, L;

Publication
Theory Comput. Syst.

Abstract