Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BRUNO LOFF:
All reports by Author Bruno Loff:

TR18-175 | 23rd October 2018
Bruno Loff, Sagnik Mukhopadhyay

Lifting Theorems for Equality

Revisions: 1

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>


TR17-170 | 6th November 2017
Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Simulation Beats Richness: New Data-Structure Lower Bounds

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>


TR17-014 | 23rd January 2017
Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Composition and Simulation Theorems via Pseudo-random Properties

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>


TR16-165 | 30th October 2016
Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Lower Bounds for Elimination via Weak Regularity

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>


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 >>>


TR12-054 | 2nd May 2012
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

Reductions to the set of random strings:the resource-bounded case

Revisions: 1

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>




ISSN 1433-8092 | Imprint