All reports by Author Marco Molinaro:

__
TR15-031
| 2nd March 2015
__

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev#### Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

__
TR12-076
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Testing Lipschitz Functions on Hypergrid Domains

__
TR12-075
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Limitations of Local Filters of Lipschitz and Monotone Functions

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>