Interplay of Geometry and Computation: Fall'21Seminar 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 scheduleDescription of TopicsHardness and Approximation of k-center in L_p metricsIn 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: CoresetsMinimizing 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 PracticeIn practice, clustering tasks are popularly carried out using Llyod's algorithm with particularemphasis 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 metricsIn 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 metricIf the input to TSP is a point-set from the L_p metric space, can we utilize the geometryof 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 NormIn this meeting we are learning about the computational aspects of the Brouwer's fixed-point theoremin 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 NormIn a breakthrough work, [R16] proved a collection of important results, one of which showedthat 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 HalvingA fair way for roommates to divide the monthly rent is intimately connected with the questionof 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]. Low Degree Polynomial TestsLow Degree Testing, the problem of testing the proximity of a function to a family of low-degreepolynomials 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. Approximation of Closest Pair: Locality Sensitive HashThe closest pair problem [Wiki] in constant dimensions was among the first geometric problemsthat 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 MethodDespite 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 PairIn a breakthrough work, [ARW17] proved the first hardness of approximation results infine-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 ProblemThe 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]. |