A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**J**

__
TR21-177
| 22nd November 2021
__

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee#### Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics

__
TR21-004
| 10th January 2021
__

Vishnu Iyer, Avishay Tal, Michael Whitmeyer#### Junta Distance Approximation with Sub-Exponential Queries

__
TR13-042
| 25th March 2013
__

Siu Man Chan#### Just a Pebble Game

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

k-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in $\ell_p$-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives ... more >>>

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

Siu Man Chan

The two-player pebble game of Dymondâ€“Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>