Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jop Briet:

TR14-026 | 27th February 2014
Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

Lower Bounds for Approximate LDCs

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

TR10-048 | 24th March 2010
David GarcĂ­a Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Monotonicity Testing and Shortest-Path Routing on the Cube

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

ISSN 1433-8092 | Imprint