**Usual time and location:** Wednesdays at 1:00pm, HAAS, Room 175 unless noted otherwise (e.g., for visitors from out of town, or scheduling conflicts when booking the room.).

**Organizers Spring ’20:** **Alexander Block**, **Simina Brânzei**, and **Kent Quanrud**.

**Mailing List:** theory-cs-seminar@lists.purdue.edu (join here)

## Spring 2020 Schedule:

**February 5:** **Shubhang Kulkarni** (Purdue). *Algorithmic Approximation Techniques for Directed Orienteering and Directed Steiner Trees*. Abstract below.

**February 12:** **Minshen Zhu** (Purdue). *Detecting Multilinear Terms in Polynomials and Applications to Finding Connected Subgraphs.* Abstract below.

**February 19:** *No speaker.*

**February 26:** **Kent Quanrud** (Purdue). * A Linear-time Algorithm for Finding a Sparse k-connected Spanning Subgraph of a k-connected Graph.* Abstract below.

**March 4:** **Tamalika Mukherjee** (Purdue). *Fine-grained complexity of SVP. *Abstract below.

**March 11:** *No speaker (Spring Break)*

**April 8:** **Shai Ben-David**.

**April 17 @ 1pm EST:** **Nima Anari**. *Note the change in the day.*

**April 22:**

**April 29:**

## Fall 2019 Schedule:

**August 29: Arturs Backurs** (Toyota Technological Institute at Chicago). *Efficient Density Evaluation for Smooth Kernels*. Abstract below.

**September 3**: **Tamal Dey** (Ohio State University). *Certified Algorithms in Topological Shape and Data Analysis*. Abstract below.

**September 10: Akash Kumar** (Purdue). *Max Cut, SDPs and Sum-of-Squares. * Abstract below.

**September 18 (Wednesday): Minshen Zhu **(Purdue). *High-Dimensional Expanders and Applications.* Abstract below.

**September 25 (Wednesday): Shai Vardi** (Purdue). *How to Hire Secretaries with Stochastic Departures*. 1:00PM at Room 3102. Abstract below.

**October 4 (Friday): Kent Quanrud. ***Graph partitioning using single commodity flows* (by Khandekar, Rao, Vazirani). 2:00 PM, LWSN 3102.

**October 9** **(Wednesday)**: **Steve Hanneke** (Toyota Technological Institute at Chicago)

**October 17:** **Alex Block**. *(Zero-Knowledge) Interactive Proofs (Survey Talk)*. 1:30PM to 2:30 PM in LWSN 3102. Abstract below.

**October 24:** **Tamalika Mukherjee**. *Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP*. 1:30 PM to 2:30 PM in LWSN 3102. Abstract below.

**October 31:** **Young-San Lin**. *Approximate Welfare Maximization in Combinatorial Auctions (Survey Talk).* 1:30 PM to 2:30 PM in LWSN 3102. Abstract below.

**November 7:** **Adrian Vladu** (Boston University). *Improved Convergence for L∞ and L1 Regression via Iteratively Reweighted Least Squares.* 1:30 PM to 2:30 PM in LWSN 3102. Abstract below.

**November 14: Visu Makam **(Institute for Advanced Study). *Barriers for lifting techniques for tensor rank lower bounds*. 1:30 to 2:30 PM in LWSN 3102. Abstract below.

* Visu is also speaking in the Algebraic Geometry Seminar (in the math department) on November 13 on the topic “Singular tuples of matrices is not a null cone”.

**November 20: Lance Fortnow** (Illinois Institute of Technology). * Distinguished Theory Seminar*, 11:30 AM to 12:30 PM in LWSN 1142.

**December 5:** **Jug****al Garg** (UIUC). TBD

1:30 PM to 2:30 PM in LWSN 3102.

# Abstracts:

**March 4: Tamalika Mukherjee**. *Fine-grained complexity of SVP*. 1:00pm to 2:00pm in HAAS 175.

Abstract: The Shortest Vector Problem (SVP) in lattices has been a long-standing problem of interest in the mathematics community and more recently has gained a lot of interest in the computer science community due to its role in lattice-based cryptographic constructions. Loosely speaking, the security of many of these cryptographic primitives is based on the worst-case hardness of SVP, and these primitives are likely to be used on a mass scale in the near future.

In this talk we will survey some initial hardness results of SVP and then mainly focus on the fine-grained hardness results which were recently shown in a STOC 2018 paper titled “(Gap/S)ETH Hardness of SVP”, by Divesh Aggarwal and Noah Stephens-Davidowitz.

**February 26:** **Kent Quanrud**. *A Linear-time Algorithm for Finding a Sparse k-connected Spanning Subgraph of a k-connected Graph*. 1:00pm to 2:00pm in HAAS 175.

Abstract: In this talk, Kent presents the algorithm introduced by this work of Nagamochi and Ibaraki (Algorithmica 1992). The original abstract is below.

We show that any k-connected graph G = (V, E) has a sparse k-connected spanning subgraph G’ = (V, E’) with |E’| = O(k |V|) by presenting an O(|E|)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time bound O( max{ k^2 |V|^(1/2), k |V| } |E| ) to determine whether node-connectivity \kappa(G) of a graph G = (V, E) is larger than a given integer k or not can be reduced to O( max{ k^3 |V|^(3/2), k^2 |V|^2 } ).

**February 12: Minshen Zhu**. *Detecting Mulilinear Terms in Polynomials and Applications to Finding Connected Subgraphs*. 1:00pm to 2:00pm in HAAS 175.

Abstract: Suppose we have a polynomial P(x_1, x_2, …, x_n) of total degree k (over some finite field) which is implicitly defined by an arithmetic circuit of size poly(n). We are interested in the following multilinear-term detecting problem: in the sum-of-product expansion of P is there a monomial involving at most one copy of each variable? Such a monomial is named a multilinear term. In this talk I will introduce a 2^k*poly(n)-time randomized algorithm for this problem, and show that such an algorithm implies fixed-parameter tractable (FPT) algorithms for k-Path and k-Tree, and more generally problems of finding connected subgraphs of size k in a given graph.

**February 5:** **Shubhang Kulkarni**. *Algorithmic Approximation Techniques for Directed Orienteering and Directed Steiner Trees*. 1:00pm to 2:00pm in HAAS 175.

Abstract: Several important combinatorial optimization problems may be formulated as finding certain paths, tours or constrained subgraphs in a graph. Famous problems such as the traveling salesman problem, Chinese postman problem, minimum spanning tree, etc., aim to minimize the “tour” length subject to certain constraints on the nodes visited by the tour. Another class of problems is the prize-collecting traveling salesman/repairman problem which seeks to maximize some function (reward) of the nodes visited during the tour subject to constraints on the tour taken.

This talk will be a survey talk which will introduce a few interesting algorithmic techniques that have been used to tackle problems of the latter flavor. In particular, we will focus on the orienteering problem (and a few generalizations): given a directed edge-weighted graph, source-sink vertices S-T, and a path budget, find an S-T path which visits a maximum number of nodes subject to the weight of the path being within the budget.

I will discuss a surprisingly simple quasi-polynomial algorithm inspired by Savitch’s theorem that achieves a logarithmic approximation to this problem, even when the objective function is any submodular function on the subset of nodes visited. I will further show how to generalize this algorithm to handle the rooted directed tree-orienteering problem, which aims to find a rooted tree instead of an S-T path in the above problem formulation. Finally, time permitting, I hope to discuss connections of these techniques to multi-trees, which are combinatorial structures that have recently been used for quasi-polynomial time approximation algorithms for variants of the directed Steiner Tree problem.

**November 20: Lance Fortnow** **(Distinguished Theory Talk)**. Title: *The Early Days of Interactive Proofs.*

Abstract: Consider the clique problem, given a graph is there a collection of vertices of a given size that are all connected to each other. A powerful wizard could convince you that a large clique exists, just provide the set of vertices and you can check that all pairs are connected. This notion made formal the class NP, the basis of the famous P v NP problem.

What if the wizard wanted to convince you that no clique existed? You would seemingly need to check all large subsets. Thirty years ago, Lund, Fortnow, Karloff and Nisan showed that a wizard can convince a mere mortal, if the mortal can ask random questions. Shamir shortly thereafter extended these results to everything computable in a reasonable amount of memory, the IP = PSPACE result.

This talk will go over the early history of IP = PSPACE and how then new email technologies played a critical role. We then give an overview of how interactive proofs and related probabilistically checkable proofs have transformed how we think about efficient computation.

**November 14: Visu Makam **(Institute for Advanced Study). *Barriers for lifting techniques for tensor rank lower bounds*.

One common set of techniques for lower bounds, which is ancient but whose prominence and use increases with recent successes (and realization that past methods fit this mold) are lifting (or escalation) techniques. Here one aims to derive a lower bound for some strong model, via a reduction to proving a related lower bound on a weaker model.

The two main complexity measures that we will consider are tensor rank (for tensors) and Waring rank (for polynomials). We will show strong barriers to lifting lower bounds from lower degree tensors/polynomials to higher degree tensors/polynomials, significantly generalizing the result in [EGOW18] which gives barriers to lifting matrix rank lower bounds to tensors/polynomials. The key new ingredient is a statement in algebraic geometry very similar to the implicit function theorem that we will explain. This is joint work with Ankit Garg, Rafael Oliveira and Avi Wigderson.

**November 7:** **Adrian Vladu** (Boston University). *Improved Convergence for L∞ and L1 Regression via Iteratively Reweighted Least Squares.* 1:30 PM to 2:30 PM in LWSN 3102.

The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed, but theoretical analyses usually fail to capture their good practical performance.

I will present a simple and natural version of IRLS for solving L∞ and L1 regression, which provably converges to a (1+ε)-approximate solution in O(m^1/3 log(1/ε)/ε^(2/3) + log(m/ε)/ε^2) iterations, where m is the number of rows of the input matrix. This running time is independent of the conditioning of the input, and up to poly(1/ε) beats the O(m^1/2) iterations required by standard interior-point methods.

This improves upon the highly specialized algorithms of Chin et al. (ITCS ’12), and Christiano et al. (STOC ’11), and yields a truly efficient natural algorithm for the slime mold dynamics (Straszak-Vishnoi, SODA ’16, ITCS ’16, ITCS ’17).

I will also highlight a few connections to packing/covering LP solvers and higher order optimization methods.

Arxiv link: https://arxiv.org/pdf/1902.06391.pdf, appears in ICML 2019.

**October 31:** **Young-San Lin**. *Approximate Welfare Maximization in Combinatorial Auctions (Survey Talk) *. 1:30 PM to 2:30 PM in LWSN 3102.

We explore how social welfare can be approximately maximized in combinatorial auctions when goods are indivisible. Each buyer has a valuation function on a set of items, which is of exponential size thus one must specify how it can be accessed. The types of queries that have been considered are value and demand queries.

We will start with a 2-approximation greedy algorithm for submodular valuations with value queries as a warm up. Then show how demand queries can be used to solve a relaxed linear program (LP) for welfare maximization. Finally, given a fractional solution from the relaxed LP, we will discuss some rounding techniques for subadditive and fractionally subadditive valuations.

**October 24:** **Tamalika Mukherjee**. *Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP*. 1:30 PM to 2:30 PM in LWSN 3102.

We show how to generalize lattice reduction algorithms to module lattices in order to reduce γ-approximate ModuleSVP over module lattices with rank k≥2 to γ′-approximate ModuleSVP over module lattices with rank 2≤β≤k. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a higher-dimensional analogue of the (Z-)basis of a lattice. The particular value of γ that we achieve depends on the underlying number field K, the ring R⊂K, and the embedding (as well as, of course, k and β). However, for reasonable choices of these parameters, the approximation factor that we achieve is surprisingly close to the one achieved by “plain” lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension.

In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehlé, and Wallet, which works in the important special case when β=2 and R=OK is the ring of integers of K under the canonical embedding. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that slide reduction generalizes LLL reduction.

**October 17:** **Alex Block**. (Zero-Knowledge) Interactive Proofs (Survey Talk). 1:30PM to 2:30 PM in LWSN 3102.

Abstract: In this talk, we explore the power of interactive proofs and their zero-knowledge variant. The idea of (zero-knowledge) proofs was introduced by Goldwasser, Micali, and Rackoff [GMR89] and has since then been the subject of intense study in various different fields, including complexity theory and cryptography. An interactive proof is a protocol in which a (computationally unbounded) prover convinces a (efficient) verifier that some statement is true. It is crucial that for any true statement, any honest prover can convince a verifier of a with high probability, and for any false statement, any cheating prover cannot convince a verifier the statement is true. This simple setup admits many powerful results; we’ll touch upon a few of these.

We will also discuss zero-knowledge interactive proofs. An interactive proof is zero-knowledge if (roughly speaking) the only information a verifier learns from viewing the transcript is whether or not the statement is true or false. That is, a verifier learns nothing more than the validity of the statement being proven. We’ll conclude with an examination of some results related to zero-knowledge proofs.

**September 25: Shai Vardi** (Purdue). **Title:** How to Hire Secretaries with Stochastic Departures

We study a generalization of the secretary problem, where decisions do not have to be made immediately upon candidates’ arrivals. After arriving, each candidate stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this candidate or not. The goal is to maximize the probability of selecting the best candidate overall. We assume that the arrival waiting times are drawn from known distributions.

Our first main result is a characterization of the optimal policy for this setting. We show that when deciding whether to select a candidate it suffices to know only the time and the number of candidates that have arrived so far. Furthermore, the policy is monotone non-decreasing in the number of candidates seen so far, and, under certain natural conditions, monotone non-increasing in the time. Our second main result is proving that when the number of candidates is large, a single threshold policy is almost optimal. Joint work with Thomas Kesselheim (University of Bonn) and Alex Psomas (Simons/Purdue CS)

Bio: Shai is an Assistant Professor of Management Information Systems at the Krannert School of Management at Purdue University. He received his PhD in Computer Science from Tel Aviv University, and was a Linde Postdoctoral Fellow at SISL at Caltech. His research interests include game theory, fairness and dynamic mechanism design.

**September 18: Minshen Zhu **(Purdue). **Title:** High-Dimensional Expanders and Applications (Survey talk, paper by Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant, STOC 2019).

Abstract: Expander graphs are very useful objects in theoretical computer science. This is because expander graphs can be studied from different perspectives. We can view expander graphs as: (1) a sparser version of the complete graph satisfying some expansion properties, (2) graphs on which random walks mixes rapidly, (3) “pseudorandom” version of random graphs. High-dimensional expanders (HDXs) are high-dimensional counterparts of such objects, usually defined in terms of simplicial complexes, which can be roughly thought of as “expanding hypergraphs”. While normal expander graphs admit so many (equivalent) characterizations, it is unclear which one should be adopted when generalizaing them to hypergraphs. In this talk I will introduce several definitions of HDXs, including link expanders and random walk expanders, and show some connections between them. I will introduce the so-called “Garland’s method” and use it to prove Oppenheim’s “Trickling Down” Theorem, which relates local expansion with global expansion. If time permits, I will use this result to show the bases-exchange chain of a matroid mixes rapidly, thus giving an FPRAS for sampling bases of a matroid.

**September 10: Akash Kumar** (Purdue). **Title:** Max Cut, SDPs and Sum-of-Squares. (Survey talk).

Abstract: This will mostly be a survey of the literature around Max-Cut, SDPs and Sum-of-Squares. Max-Cut is a classical problem exploring which has led to huge advances in the design of approximation algorithms. Some of the ideas used in the famed Goemans Williamson Rounding (which we will cover) continue influencing including some recent developments — two examples which come to mind are [Charikar-Makarychev-Makarychev-09, Montanari-Zhou 16]. We will use this as an opportunity to revisit the sum-of-squares literature. We will finish with a discussion of some open problems in the area.

Bio: I am a PhD student in the CS department. I am being advised by Professor Suagata Basu.

Abstract: In the past two decades, topological data analysis, an area seeded by computational geometry and topology, has emphasized processing shapes and data from the topological viewpoint in addition to geometry. The understanding of topological structures in the context of computations has resulted into sound algorithms and has also put a thrust in developing further synergy between mathematics and computations in general. This talk aims to explain this perspective by considering some applications in shape and data analysis, namely, (i) surface/manifold reconstructions, (ii) mesh generation, and (iii) feature extraction by persistent homology. For the first two topics, we will emphasize the role of topology, state some of the key results while for the third we will go a little deeper to explain how topology can delineate signal from noise more robustly in a scale-invariant manner. The hope is that the talk will further stimulate the interest in tying topology and computation together in the larger context of data science.

Bio: Tamal K. Dey is a professor of computer science at The Ohio State University where he is currently serving as the Interim Chair of the CSE department. His research interest includes computational geometry, computational topology and their applications to geometric modeling and data analysis. He finished his PhD from Purdue University in 1991. Prior to joining OSU, he held academic positions at University of Illinois at Urbana Champaign, Indiana University-Purdue University at Indianapolis, Indian Institute of Technology, Kharagpur, India, and Max-Planck Institute, Germany. He has (co)authored two books “Curve and surface reconstruction: Algorithms with Mathematical Analysis” published by Cambridge University Press and “Delaunay Mesh Generation” published by CRC Press. (Co)author of more than 200 scientific articles, Dey is an IEEE and ACM Fellow. He serves in various editorial and executive boards and routinely gives invited lectures at various academic forums. He leads the Jyamiti research group at OSU and heads the recent NSF sponsored TRIPODS Phase I Institute at OSU. Details can be found at https://web.cse.ohio-state.edu/~dey.8.

**August 29: Arturs Backurs** (Toyota Technological Institute at Chicago). **Title**: Efficient Density Evaluation for Smooth Kernels

Abstract: Given a kernel function k and a dataset P (of points from R^d), the kernel density function of P at a point q from R^d is equal to KDF_P(q) := 1/|P| sum_{p in P} k(p,q). Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDF_P(q) quickly, often for many inputs q and large point-sets P. In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is “smooth”, i.e., the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log(Phi n)/eps^2) preprocessing, estimates KDF_P(q) up to a factor of 1+eps in O(d log (Phi n)/eps^2) time, where Phi is the aspect ratio. The log(Phi n) term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples.

We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than l_2. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1+eps)-approximate estimation algorithms for kernels over other l_p norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for l_p norms and other spaces.

Joint work with Moses Charikar, Piotr Indyk and Paris Siminelakis.

Bio: Arturs Backurs is a Research Assistant Professor at the Toyota Technological Institute at Chicago (TTIC). He received Ph.D. degree from MIT in 2018. He previously received his bachelor’s degree from University of Latvia in 2012.

His research area is theoretical computer science with the main focus on proving conditional lower bounds for problems that are solvable in polynomial time as well as designing faster algorithms inspired by the hardness results.