TOC Group links
TOC Home
TOC Calendar
Seminars
TOC Colloquium
A&C Seminar
CIS Seminar
Theory Lunch
Harvard/MIT/MSR
Reading Group

Algorithms & Complexity Seminar, MIT : Fall 2021-Spring 2022

Organizers: Noah Golowich (nzg AT mit DOT edu), Rahul Ilango (rilango AT mit DOT edu)

The Algorithms & Complexity Seminar will usually (unless otherwise stated) meet on Wednesdays 4pm-5pm virtually (see below for Zoom links). The style and format of these meetings are variable. Please feel free to contact the organizers to find out more details. To receive announcements of upcoming talks, subscribe to the mailing list by either visiting the mailman page or send an empty email to compalgsem-subscribe@lists.csail.mit.edu.

Upcoming Talks

Past Talks

  • Wednesday, December 15, 2021: Santhoshini Velusamy (Harvard University). [Time: 4-5pm EDT: Zoom Link]
    Topic. Approximability of CSPs with linear sketches
    Abstract. The class of constraint satisfaction problems (CSPs) includes but is not limited to optimization problems such as Max-CUT, Max-DICUT, Max-k-SAT, Max-q-Coloring, and Unique Games. In this talk, I will describe our recent results giving new upper and lower bounds on the approximability of every CSP in the single-pass streaming setting. In particular, for sketching algorithms, we prove the following dichotomy theorem: Any CSP is either solvable in polylogarithmic space or requires at least sqrt(n) space. We also prove stronger streaming lower bounds for some CSPs, significantly generalizing the previous works on Max-CUT. I will conclude with some interesting open problems in this direction. No background in streaming, sketching or constraint satisfaction problems will be needed to enjoy this talk! Based on joint works with Chi-Ning Chou, Alexander Golovnev, and Madhu Sudan.
  • Wednesday, January 26, 2022: Zihan Tan (University of Chicago). [Time: 4-5pm EDT: Zoom Link]
    Topic. Improved Approximation Algorithms of Graph Crossing Number
    Abstract. Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a O ̃(√n)-approximation, while the best current negative results do not rule out constant-factor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set E’of edges (called a planarizing set) such that G \ E’ is planar; compute a planar drawing of G \ E’; then add the drawings of the edges of E to the resulting drawing. Unfortunately, there are examples of graphs G, in which any implementation of this method must incur Ω(OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O ̃(√n)-approximation. We propose a new paradigm that allows us to overcome this barrier. Using the new paradigm, we reduce the Crossing Number problem to Crossing Number with Rotation System – a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. We then show a randomized algorithm for this new problem, that allows us to obtain a subpolynomial approximation for Graph Crossing Number on low-degree graphs. This talk is based on joint work with Julia Chuzhoy and Sepideh Mahabadi.
  • Tuesday, February 22, 2022: Ryan Williams (MIT). [Time: 4-5pm EDT in G575 (in person!) (Note the special date.)
    Topic. On the Usefulness of Believing in Something and AMA
    Abstract. I will talk about how I have failed to refute the Strong Exponential Time Hypothesis (SETH), and mention a few of the cool theorems I proved while failing miserably. Then I will let you ask me questions about anything (your questions don't have to be related to SETH).
  • Wednesday, February 23, 2022: Abhishek Shetty (UC Berkeley). [Time: 4-5pm EDT: Zoom Link]
    Topic. Matrix Discrepancy via Quantum Communication
    Abstract. In this talk, we will discuss a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spencer conjecture. In particular, we show that for every collection of $n$ $n \times n$ symmetric matrices $A_1 \dots A_n$ with spectral norm bounded by 1 and Frobenius norm bounded by$n^{1/4}$, there is a signing $x$ such that $|| \sum x_i A_i|| \leq \sqrt{n}$ We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such a sign. The proof of our main result combines a simple compression scheme for transcripts of repeated (quantum) communication protocols with quantum state purification, the Holevo bound from quantum information, and tools from sketching and dimensionality reduction. Our approach also offers a promising avenue to resolve the Matrix Spencer conjecture completely -- we show it is implied by a natural conjecture in quantum communication complexity. The talk is based on joint work with Sam Hopkins (MIT) and Prasad Raghavendra (UC Berkeley).
  • Wednesday, March 2, 2022: Sepehr Assadi (Rutgers University). [Time: 4-5pm EDT: Zoom Link]
    Topic. Deterministic Graph Coloring in the Streaming Model
    Abstract. Abstract: Recent breakthroughs in graph streaming have led to the design of single-pass semi-streaming algorithms for various graph coloring problems such as (Δ+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work. In this talk, we will discuss our recent result that fully resolves this question: there is no deterministic single-pass semi-streaming algorithm that given a graph G with maximum degree Δ, can output a proper coloring of G using any number of colors which is sub-exponential in Δ. The proof is based on analyzing the multi-party communication complexity of a related communication game using elementary random graph theory arguments. Based on joint work with Andrew Chen (Cornell) and Glenn Sun (UCLA).
  • Wednesday, March 30, 2022: Ewin Tang (University of Washington). [Time: 4-5pm EDT: Zoom Link]
    Topic. Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
    Abstract. Hamiltonian learning is the problem of learning a geometrically local N-qubit Hamiltonian H to precision ɛ, supposing we are given copies of its Gibbs state ρ = exp(-βH) / Tr(exp(-βH)) at a known inverse temperature β. This is the quantum generalization of the problem of parameter learning Markov Random Fields. I will present an algorithm that solves this problem with optimal sample complexity (number of copies of ρ needed) and optimal time complexity in the high-temperature (low β) regime. This improves on the previous best algorithm given by Anshu et al. (FOCS 2020), for the high-temperature regime. This work was done jointly with Jeongwan Haah and Robin Kothari.
  • Friday, April 8, 2022: Clayton Sanford (Columbia). [Time: 4-5pm EDT: Building 32, G575] (Note the special date.)
    Topic. On the Approximation Power of Two-Layer Networks of Random ReLUs
    Abstract. This talk discusses the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upper and lower bounds for L2-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms. Our positive results employ tools from harmonic analysis and ridgelet representation theory, while our lower-bounds are based on (robust versions of) dimensionality arguments. I'll discuss these results and their implications to depth separation and the hardness of learning sinusoidal functions with gradient descent with deeper neural networks.
  • Wednesday, April 13, 2022: Rahul Santhanam (Oxford). [Time: 2-3pm EDT: Zoom Link] (Note the special time.)
    Topic. Errorless vs Error-Prone Average-Case Hardness
    Abstract. We study the relationship between errorless and error-prone versions of average-case complexity. We show that the question of whether errorless hardness for NP implies error-prone hardness is closely tied to the long-standing open question of whether there are instance checkers for NP. We also show unconditionally that error-prone and errorless hardness are equivalent for the P vs NC^1 and UP \cap coUP vs P problems. Finally, we apply our results to get new equivalences between hitting set generators and pseudo-random generators. Based on joint work with Shuichi Hirahara (NII, Tokyo).
  • Thursday, April 14, 2022: Roei Tell (IAS/DIMACS). [Time: 4-5pm EDT in 32-D451] (Note the special date and location.)
    Topic. Hardness vs randomness without PRGs, and derandomizing interactive protocols without paying for it
    Abstract. Can we build a hardness to randomness framework that doesn't rely on classical pseudorandom generators (PRGs)? And can we remove randomness from interactive proof systems without paying for it in runtime overheads? This self-contained talk will follow up on Tuesday's colloquium talk, and will focus on two very recent results, from works with Lijie Chen. First, we'll see how to deduce that BPP = P without classical PRGs, relying instead on non-black-box algorithmic techniques. This allows us to avoid assuming classical circuit lower bounds, and instead assume a new type of lower bounds for uniform probabilistic algorithms. We will show two-way connections between the promiseBPP = promiseP conjecture and this new type of lower bounds. Secondly, we'll see how to transform every constant-round interactive protocol into a NP-type verifier that has essentially the same time complexity and that looks sound to any efficient adversary (under strong hardness assumptions). Consequently, for every eps>0, we conditionally construct a deterministic argument system for counting the number of satisfying assignments for an n-bit formula of size 2^{o(n)} in time 2^{eps*n}, with soundness against adversaries running in time 2^{O(n)}.
  • Wednesday, April 20, 2022: Igor Oliveira (University of Warwick). [Time: 4-5pm EDT Zoom Link]
    Topic. Extracting computational hardness from classical and quantum learning algorithms
    Abstract. I will explain how to obtain a hard computational problem from a non-trivial learning algorithm for a circuit class C. Results of this form can be interpreted in different ways. For an optimist, they offer a path to breakthroughs in complexity theory via the discovery of slightly better algorithms. On the other hand, for a pessimist, they might serve as an explanation for the difficulty of designing and analyzing learning algorithms for more expressive classes of functions, even in the quantum setting. The talk will provide an accessible introduction to results of this form and cover some ideas from a joint work with Srinivasan Arunachalam, Alex Grilo, Tom Gur, and Aarthi Sundaram (https://arxiv.org/abs/2012.01920).
  • Thursday, April 21, 2022: Max Hopkins (UCSD). [Time: 4-5pm EDT in 32-G575] (Note the special date.)
    Topic. Hypercontractivity and Small-Set Expansion on High Dimensional Expanders.
    Abstract. Hypercontractivity is one of the most powerful tools in Boolean function analysis. Traditionally studied on the Boolean cube, recent years have seen a number of exciting applications of hypercontractivity on extended domains, most famously including the resolution of Khot’s 2-2 games conjecture. Despite such impressive applications, however, our general understanding of hypercontractivity actually remains remarkably poor, with few known examples and complicated, domain-specific proofs. In this talk, we discuss the first steps towards a unified theory of hypercontractivity based on high dimensional expanders (HDX), a broad class of hypergraphs that have recently seen a series of breakthrough applications in coding theory and approximate sampling. We’ll pay special attention to the motivating application of characterizing small-set expansion in graphs, and briefly discuss how the line of work could lead to new insights towards resolving the unique games conjecture. Based on joint work with Mitali Bafna, Tali Kaufman, and Shachar Lovett to appear at STOC 2022.
  • Wednesday, April 27, 2022: Ruta Mehta (UIUC). [Time: 4-5pm EDT: Zoom Link]
    Topic. Allocating Goods, Bads, and Mixed: Fairness and Efficiency through Competitiveness
    Abstract. Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are nondisposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed). I will first consider the case of additive valuations, where when all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this non-convexity through a novel exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise monotone function over linear constraints. Finally, I will discuss extensions to general utility functions, and recent developments on the exchange setting (barter system). Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin.

Theory Calendar

Add this calendar to yours to receive details about upcoming events in the Theory group
(includes A&C Seminars, TOC Colloquium, CIS Seminars, Theory Lunch, TOC tea and more!) :


Click on the events above to get more description about the same (title/abstract for talks, etc.)

Earlier Editions of A&C Seminar