Bruno Loff

Bruno Loff

Auto-generated profile, based on publicly available information

Bruno Loff

Instituto Superior Técnico, Technical University of Lisbon1049-001 Lisbon, Portugal

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
31 May 2014
Verified
Conference Paper
Open access
HBHarry Buhrman
Harry Buhrman
RCRichard Cleve
Richard Cleve
MKMichal Koucký
Michal Koucký
BLBruno Loff
Bruno Loff
FSFlorian Speelman
Florian Speelman
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 when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform TC1-circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. TC1-circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace. In order to obtain our results we study an algebraic model of computation, a variant of straight-line programs. We employ register machines with input registers x1,..., xn and work registers r1,..., rm. The instructions available are of the form ri ← ri±u×v, with u, v registers (distinct from ri) or constants. We wish to compute a function f(x1,..., xn) through a sequence of such instructions. The working registers have some arbitrary initial value ri = τi, and they may be altered throughout the computation, but by the end all registers must be returned to their initial value τi, except for, say, r1 which must hold τ1 + f(x1,..., xn). We show that all of Valiant's class VP, and more, can be computed in this model. This significantly extends the framework and techniques of Ben-Or and Cleve [6]. Upper bounding the power of catalytic computation we show that catalytic logspace is contained in ZPP. We further construct an oracle world where catalytic logpace is equal to PSPACE, and show that under the exponential time hypothesis (ETH), SAT can not be computed in catalytic sub-linear space.

18 July 2019 in computational complexity
Verified
Journal Article
Open access
PDF file
ACArkadev Chattopadhyay
Arkadev Chattopadhyay
MKMichal Koucký
Michal Koucký
BLBruno Loff
Bruno Loff
SMSagnik Mukhopadhyay
Sagnik Mukhopadhyay
We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999), to any gadget which satisfies a certain hitting property. We prove that inner product and gap-Hamming satisfy this property, and as a corollary, we obtain a deterministic simulation theorem for these gadgets, where the gadget’s input size is logarithmic in the input size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Göös, Pitassi & Watson (in: Proceedings of the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in the deterministic communication complexity and the logarithm of the 1-partition number, no matter how high the 1-partition number is with respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (2015).

24 June 2008 in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Verified
Journal Article
Closed access
PDF file
EBEdwin J. Beggs
Edwin J. Beggs
JCJosé Félix Costa
José Félix Costa
BLBruno Loff
Bruno Loff
JTJohn V Tucker
John V Tucker
We discuss combining physical experiments with machine computations and introduce a form of analogue–digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.

12 January 2016 in Algorithmica
Verified
Journal Article
Open access
PDF file
JBJoshua Brody
Joshua Brody
HBHarry Buhrman
Harry Buhrman
MKMichal Koucký
Michal Koucký
BLBruno Loff
Bruno Loff
FSFlorian Speelman
Florian Speelman
NVNikolay Vereshchagin
Nikolay Vereshchagin
Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with but 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 convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct-sum theorems through the compression of interactive communication in the bounded-round setting. To obtain this application, we prove a new one-shot variant of the Slepian–Wolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newman’s Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

15 June 2017 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
HBHarry Buhrman
Harry Buhrman
MKMichal Koucký
Michal Koucký
BLBruno Loff
Bruno Loff
FSFlorian Speelman
Florian Speelman
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.

25 February 2009 in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Verified
Journal Article
Closed access
EBEdwin Beggs
Edwin Beggs
JCJosé Félix Costa
José Félix Costa
BLBruno Loff
Bruno Loff
JTJ.V. Tucker
J.V. Tucker
Earlier, to explore the idea of combining physical experiments with algorithms, we introduced a new form of analogue–digital (AD) Turing machine. We examined in detail a case study where an experimental procedure, based on Newtonian kinematics, is used as an oracle with classes of Turing machines. The physical cost of oracle calls was counted and three forms of AD queries were studied, in which physical parameters can be set exactly and approximately. Here, in this sequel, we complete the classification of the computational power of these AD Turing machines and determine precisely what they can compute, using non-uniform complexity classes and probabilities.