Next

__
TR18-211
| 3rd December 2018
__

Kshitij Gajjar, Jaikumar Radhakrishnan#### Parametric Shortest Paths in Planar Graphs

__
TR18-210
| 30th November 2018
__

Karthik C. S., Pasin Manurangsi#### On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

__
TR18-209
| 8th December 2018
__

Emanuele Viola#### AC0 unpredictability

Next

Kshitij Gajjar, Jaikumar Radhakrishnan

We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

Karthik C. S., Pasin Manurangsi

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

Emanuele Viola

We prove that for every distribution $D$ on $n$ bits with Shannon

entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of

the bits $D_{i}$ can be predicted with advantage $\gamma$ by an

AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of

all the bits of $D$ except $D_{i}$. ...
more >>>

Next