Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Florian Speelman:

TR14-053 | 15th April 2014
Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

Computing with a full memory: Catalytic space

Revisions: 1

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

TR12-179 | 13th December 2012
Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

ISSN 1433-8092 | Imprint