All reports by Author Jop Briet:

__
TR14-026
| 27th February 2014
__

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf#### Lower Bounds for Approximate LDCs

__
TR10-048
| 24th March 2010
__

David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

We study an approximate version of $q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A $q$-query $(\alpha,\delta)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $\Omega(\delta n)$ ... more >>>

David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>