Interplay of Geometry and Computation: Fall'21


Seminar in Computer Science (16:198:671)
Monday: 17:00-20:00
Hill 116


In the first meeting, I will briefly introduce each of the topics that will be presented in this course.
In subsequent meetings one or more of you will present the topics listed below.

Topics and schedule*

*subject to changes.

# When Who What
1 09/08 Karthik C. S. Brief Introduction to pool of topics
2 09/13 Janani Sundaresan and Chen Wang Hardness and Approximation of k-center in L_p metrics
3 09/20 Parth Mittal Approximate Clustering: Coresets
4 09/27 Chen Wang k-means Clustering: Theory meets Practice
5 10/04 Chengyuan Deng Hardness and Approximation of TSP in General metrics
6 10/11 Vihan Shah Hardness and Approximation of TSP in Euclidean metric
7 10/18 Vihan Shah Query Lower Bound of Brouwer Fixed Point in Max Norm
8 10/25 Karthik C. S. PPAD-Hardness of Brouwer Fixed Point in Euclidean Norm
9 11/01 Vikrant Ashvinkumar PPA-Hardness of Consensus Halving
10 11/08 Approximation of Closest Pair: Locality Sensitive Hash
11 11/15 Janani Sundaresan Approximation of Bichromatic Closest Pair: Polynomial Method
12 11/22 Chengyuan Deng Hardness of Bichromatic Closest Pair
11/29 NO LECTURE
13 12/06 Exponential Time Approximation of Closest Vector Problem
14 12/13 Surya Teja Gavva Low Degree Polynomial Tests

Description of Topics

Hardness and Approximation of k-center in L_p metrics

In this meeting we are learning about the complexity of the metric k-center problem with facilities.

There is a simple 3 factor approximation polynomial time algorithm for k-center with facilities
and this is tight for general metrics [Wiki].

But if the input is from L_p metric space, can we then utilize the geometry of the space
to get better polytime approximation algorithms?


The answer is NO for L_1 and L_inf metrics and the speaker(s) will present the hardness of
approximation results for k-center in L_p metrics that was proved in Section 2 of [FG88].

On the other hand, the answer is YES for L_2 metric, and the speaker(s) will present the
2.74 factor approximation polytime algorithm given in Section 2 of [NSS13].

Approximate Clustering: Coresets

Minimizing the Euclidean k-means clustering objective is NP-Hard even when k=2 [D08].

Suprisingly, for every fixed k, there is a polynomial time approximation scheme (PTAS)
for the Euclidean k-means clustering objective using geometric objects called coresets!

The speaker(s) will present the construction of these coresets which are described in Section 5.2
of [C09] and will also present how to use them to obtain a PTAS for Euclidean k-means problem
for fixed k (Section 6.1 of [C09]).

k-means Clustering: Theory meets Practice

In practice, clustering tasks are popularly carried out using Llyod's algorithm with particular
emphasis given to its initial seeding (noteworthy is the k-means++ seeding).

However the success of these algorithms on real-world datasets was not explained by the
theoretical analysis which showed that these algorithms were approximating k-means objective
to Ω(log k) factor in the worst case.

In [KK10], under reasonable assumptions on the input, the authors prove the success of the
above type of algorithms. The speaker(s) will present this result given in Section 5 of [KK10].

Hardness and Approximation of TSP in General metrics

In this meeting we are learning about the complexity of metric TSP.

In 1976, a simple 3/2 factor approximation polynomial time algorithm for metric TSP was
provided by Christofides. The speaker(s) will present this algorithm and its analysis.

On the other hand, it is also known that approximating TSP to a factor better than 123/122
is NP-hard and the speaker(s) will present this result of [KLS15] as well.

Hardness and Approximation of TSP in Euclidean metric

If the input to TSP is a point-set from the L_p metric space, can we utilize the geometry
of the space to obtain a polytime approximation scheme?


The answer is NO and the speaker(s) will present the hardness of approximation results
for TSP in L_p metrics that was proved in Section 3 of [T00].

On the other hand, if the dimension is fixed, then the answer is (surprisingly) YES for the
Euclidean metric as shown in [A98]. The speaker(s) will present a simpler version of this result
as given in these lecture notes, for the case when the point-set is from the Euclidean plane.

Query Lower Bound of Brouwer Fixed Point in Max Norm

In this meeting we are learning about the computational aspects of the Brouwer's fixed-point theorem
in the Max Norm.

Given a Brouwer function f: [0,1]n → [0,1]n that is constant Lipschitz continuous, one may naively
find an ε-approximate fixed point using 2O(n/ε) queries in any L_p-metric space by simply querying
on a net in [0,1]n.

In a pioneering work, [HPV89] showed that this simple deterministic query algorithm is essentially
optimal for the max norm!

Recently, in [B16], the author extended this lower bound to randomized queries. The speaker(s) will
present this result given in Sections 4.2 and 4.3 of [B16].

PPAD-hardness of Brouwer Fixed Point in Euclidean Norm

In a breakthrough work, [R16] proved a collection of important results, one of which showed
that any randomized query algorithm given as input a Brouwer function f: [0,1]n → [0,1]n that is
constant Lipschitz continuous in the Euclidean space, requires 2Ω(n/ε) queries to find an
ε-approximate fixed point.

Furthermore, in [R16] is a proof of the PPAD-completeness of an ε-approximate fixed point of a
Brouwer function in the Euclidean space. The speaker(s) will present this result given in
Section 3 of [R16].

PPA-hardness of Consensus Halving

A fair way for roommates to divide the monthly rent is intimately connected with the question
of determining if (and where) there are two diameterically opposite points on earth with the
same temperature and pressure. This is because both these problems are PPA-complete!

Recently, in [FG18,FG19], the authors proved that a host of important problems related to
fair division are all PPA-complete.

The speaker(s) will present the PPA-completeness result for the celebrated Consensus Halving
problem [Wiki], whose simplified proof is given in Section 3 of [FHSZ20].

Approximation of Closest Pair: Locality Sensitive Hash

The closest pair problem [Wiki] in constant dimensions was among the first geometric problems
that were treated at the origins of the systematic study of the computational complexity of
geometric algorithms.

However, it is known that closest pair problem in high dimensions cannot be solved in subquadratic
time. In this light, the powerful Locality Sensitive Hashing technique was developed [Wiki] in
[IM98] to approximately solve the problem in subquadratic time.

The speaker(s) will present a taste of this technique given in these lecture notes. Then, the
speaker(s) will present the near optimal LSH constructions given in [AI06].

Approximation of Bichromatic Closest Pair: Polynomial Method

Despite LSH providing highly effective approximate solutions to the closest pair problem,
the extent of it's approximation guarantees (in the worst case) were shown in [OWZ09]

At the same time, works in the flourishing area of fine-grained complexity (such as [W14]),
provided insights to use the polynomial method in algorithm design.

In a series of papers listed here, the authors provide the state-of-the-art approximation
algorithms for the closest pair problem. The speaker(s) will present one or more of these papers.

Hardness of Bichromatic Closest Pair

In a breakthrough work, [ARW17] proved the first hardness of approximation results in
fine-grained complexity. Their work provided a foundational framework to rule out
subquadratic time approximation algorithms for a host of important geometric and
string problems.

In particular, in [R18], the author rules out subquadratic algorithms for the bichromatic
closest pair problem which approximate to a factor 1+ε for some tiny ε>0.

The speaker(s) will first present Sections 3, 4, and 5 of [ARW17] and then the above result
given in Sections 3 and 4 of [R18].

Exponential Time Approximation of Closest Vector Problem

The closest vector problem is a foundational problem in lattice based cryptography [Wiki].

While the problem is NP-Hard even to approximate to any constant factor, it has motivated
the study of exponential time approximation algorithms.

The speaker(s) will present one such result given in [EHN11].

Low Degree Polynomial Tests

Low Degree Testing, the problem of testing the proximity of a function to a family of low-degree
polynomials has been intensively studied in the context of property testing and PCPs over the
last thirty years.

The analysis of these tests highlight the interplay between algebra and geometry (over finite fields).
The speaker(s) will present a simple low-degree along with its non-trivial analysis detailed in
these lecture notes.