Add to Calendar
2025-03-19 16:00:00
2025-03-19 17:00:00
America/New_York
Constructive Criticisms of Complexity: Unifying Proofs and Algorithms
For decades, fundamental questions in complexity theory have remained wide open. A classic counting argument by Shannon shows that most Boolean functions on n bits require circuits of size 2^n/n, yet we lack even superlinear circuit lower bounds for explicit functions. This raises a natural question: can we make these counting arguments constructive?In this talk, we explore constructivity through the lens of mathematical logic. Weak fragments of Peano Arithmetic, known as theories of Bounded Arithmetic, characterize "efficient" reasoning and exhibit a constructive property—proofs of existence correspond to efficient search algorithms. In particular, Buss's seminal work introduced the theories S^i_2, which capture reasoning at the i-th level of the polynomial hierarchy. We focus on S^1_2, a theory powerful enough to formalize much of modern complexity theory, from the Cook-Levin theorem to the PCP theorem.Our main results establish that:(1) Proving known, non-constructive lower bounds within S^1_2 would yield breakthrough lower bounds.(2) Under a reasonable conjecture in logic, certain circuit lower bounds are unprovable in S^1_2.These findings build on and unify previous work on constructive complexity, which traditionally employs the algorithmic notion of efficient refuters rather than bounded arithmetic. Additionally, our work provides the first conditional separation between S^1_2 and APC, a theory corresponding to ZPP reasoning.This talk is based on joint work with Marco Carmosino.
TBD
March 19
March 12
Extractors for Samplable Distributions with Low Min-Entropy
Northeastern University
Add to Calendar
2025-03-12 16:00:00
2025-03-12 17:00:00
America/New_York
Extractors for Samplable Distributions with Low Min-Entropy
Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of k = (1 − γ) · n, for some small constant γ>0. Recent work by Ball, Goldin, Dachman-Soled and Mutreja (FOCS 2023) weakened the hardness assumption. However, since the original paper by Trevisan and Vadhan, there has been no improvement in the min-entropy threshold k.In this paper we give a construction of extractors for samplable distributions with low min-entropy of k = n^{1−γ} for some constant γ, and in particular we achieve k < n/2 (which is a barrier for the construction of Trevisan and Vadhan). Our extractors are constructed under a hardness assumption that is weaker than the one used by Trevisan and Vadhan, and stronger than that used by Ball, Goldin, Dachman-Soled and Mutreja. Specifically, that there exists a constant β>0, and a problem in E = DTIME(2^O(n)) that cannot be computed by size 2^{βn} circuits that have an oracle to Σ_5.Our approach builds on the technique of Trevisan and Vadhan, while introducing new objects and ideas. We introduce and construct two objects: an errorless (seedless) condenser for samplable distributions, and functions that are hard to compute on every samplable distribution with sufficient min-entropy. We use techniques by Shaltiel and Silbak (STOC 2024), as well as additional tools and ideas, to construct the two new objects, under the hardness assumption. We then show how to modify the construction of Trevisan and Vadhan, using these new objects, so that the barrier of k=n/2 can be bypassed, and we can achieve an extractor for samplable distributions with low min-entropy.This is a joint work with Marshall Ball and Ronen Shaltiel.
TBD
March 05
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Harvard
Add to Calendar
2025-03-05 16:00:00
2025-03-05 17:00:00
America/New_York
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of better and better classical algorithms for approximating this problem. Meanwhile, another line of research has focused on porting the classical advances to various sublinear algorithm models, including semi-streaming, Massively Parallel Computation (MPC), and distributed computing. Yet, these latter works typically rely on ad-hoc approaches that do not necessarily keep up with advances in improved approximation ratios achieved by classical algorithms. This raises the following natural question: can the gains made by classical algorithms for correlation clustering be ported over to sublinear algorithms in a black-box manner? We answer this question in the affirmative by introducing the paradigm of graph de-sparsification that may be of independent interest.Joint work with Sepehr Assadi and Sanjeev Khanna.
TBD
February 20
Add to Calendar
2025-02-20 16:00:00
2025-02-20 17:00:00
America/New_York
Locally Sampleable Uniform Symmetric Distributions
We characterize the power of constant-depth Boolean circuits in generating
uniform symmetric distributions. Let f:{0,1}^m -> {0,1}^n be a Boolean
function where each output bit of f depends only on O(1) input bits. Assume
the output distribution of f on uniform input bits is close to a uniform
distribution D with a symmetric support. We show that D is essentially one
of the following six possibilities: (1) point distribution on 0^n, (2)
point distribution on 1^n, (3) uniform over {0^n,1^n}, (4) uniform over
strings with even Hamming weights, (5) uniform over strings with odd
Hamming weights, and (6) uniform over all strings. This confirms a
conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Joint
work with Daniel Kane and Anthony Ostuni.
TBD
February 19
Parallelizing Sequential Iterative Algorithms
UC Riverside
Add to Calendar
2025-02-19 16:00:00
2025-02-19 17:00:00
America/New_York
Parallelizing Sequential Iterative Algorithms
This talk will delve into our decade-long research in parallelizing
sequential iterative algorithms, such as greedy algorithms and dynamic
programming that are covered in undergrad algorithm courses. The core
concept here is to identify the inherent computational structures and
develop general frameworks for their parallel execution. I will overview
the key concepts and techniques proposed throughout this research process,
including the dependence graphs, asynchronous execution, phase parallelism,
and the cordon algorithm. Illustrative examples will include random
permutation, maximal independent set (MIS), and dynamic programming
applications. This talk will cover the results in several papers, including
a JACM'20 paper, Outstanding Papers at SPAA'20 and SPAA'24, and a best
paper at ESA'23.
TBD
February 12
A&C Seminar - Theory and applications of complete Min-CSPs: A case study in Correlation Clustering
University of Michigan
Add to Calendar
2025-02-12 16:00:00
2025-02-12 17:00:00
America/New_York
A&C Seminar - Theory and applications of complete Min-CSPs: A case study in Correlation Clustering
Abstract: We will discuss recent algorithmic results on fundamental problems in data science and clustering, including Correlation Clustering, Low-Rank Approximation, and Metric Distance Violation. A unifying theme will be their connections to Minimum Constraint Satisfaction Problems (CSPs) in complete instances. Starting from the rich theory of dense Max CSPs with several algorithmic tools (e.g., convex hierarchy, random sampling, regularity lemma), we show how this theory can be augmented to handle minimization objectives in applied domains. These efforts also inspired a systematic study on Min-CSPs in complete instances.As a technical example, we will highlight our results for Correlation Clustering, one of the most well-studied graph clustering problems. Bypassing the previous barrier of a 2-approximation based on the standard LP, we obtain a 1.44-approximation, first using a Sherali-Adams hierarchy, later also matched by a random sampling technique.
TBD
December 11
Add to Calendar
2024-12-11 16:00:00
2024-12-11 17:00:00
America/New_York
New Breakthrough in Matrix Multiplication
Abstract:Fast matrix multiplication is one of the most fundamental problems in computer science. We present new algorithms that improve the time complexity of matrix multiplication to n^2.371339, surpassing the previous bound of n^2.372860. Our result is the largest improvement to the matrix multiplication exponent since 2010. In this talk, we will introduce the modern framework for matrix multiplication algorithms and highlight the key ideas in our algorithms.
G575
December 04
Add to Calendar
2024-12-04 16:00:00
2024-12-04 17:00:00
America/New_York
From Distinguishers To Predictors and Beyond
Abstract: A central tool for constructing pseudorandom generators has been the “reconstruction paradigm” — proofs that if a generator fails to fool a circuit C, we can compute a supposedly-hard function f more efficiently with the help of C. Going from C to a small circuit for f crucially uses Yao's transformation of distinguishers to next-bit predictors. In fact, this transformation is the “bottleneck” in many results in pseudorandomness.A recent line of work has investigated the complexity of this transformation — how hard is it to turn distinguishers into predictors? Can we do it more efficiently? And what can we get out of it? I'll describe recent work that partially answers these questions, and obtains new win-win results in space complexity.Based on joint works with Dean Doron, Jiatu Li, Roei Tell, and Ryan Williams.
G575
November 20
Models That Prove Their Own Correctness
UC Berkeley
Add to Calendar
2024-11-20 16:00:00
2024-11-20 17:00:00
America/New_York
Models That Prove Their Own Correctness
Abstract: This talk introduces Self-Proving models, a new class of models that formally prove the correctness of their outputs via an Interactive Proof system. After reviewing some related literature, I will formally define Self-Proving models and their per-input (worst-case) guarantees. I will then present algorithms for learning these models and explain how the complexity of the proof system affects the complexity of the learning algorithms. Finally, I will show experiments where Self-Proving models are trained to compute the Greatest Common Divisor of two integers, and to prove the correctness of their results to a simple verifier.No prior knowledge of autoregressive models or Interactive Proofs will be assumed of the listener. This is a joint work with Noga Amit, Shafi Goldwasser, and Guy Rothblum.
G575
November 13
Add to Calendar
2024-11-13 16:00:00
2024-11-13 17:00:00
America/New_York
Gaussian Polytope Approximation
Abstract: We study the approximability of high-dimensional convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. We establish a range of upper and lower bounds both for general convex sets and for specific natural convex sets that are of particular interest. We rely on techniques from many different areas, including classical results from convex geometry, Cramér-type bounds from probability theory, and—perhaps surprisingly—a range of topics from computational complexity theory, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions. Based on joint work (https://arxiv.org/abs/2311.08575) with Anindya De and Rocco Servedio.
D507
November 06
Add to Calendar
2024-11-06 16:00:00
2024-11-06 17:00:00
America/New_York
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Abstract:We show that thermal states of local Hamiltonians are separable above a constant temperature. Specifically, for a local Hamiltonian $H$ on a graph with degree $d$, its Gibbs state at inverse temperature $\beta$, denoted by $\rho =e^{-\beta H}/ \tr(e^{-\beta H})$, is a classical distribution over product states for all $\beta < 1/(c d)$, where $c$ is a constant. This proof of sudden death of thermal entanglement resolves the fundamental question of whether many-body systems can exhibit entanglement at high temperature.Moreover, we show that we can efficiently sample from the distribution over product states. In particular, for any $\beta < 1/( c d^2)$, we can prepare a state $\eps$-close to $\rho$ in trace distance with a depth-one quantum circuit and $\poly(n, 1/\eps)$ classical overhead.
October 24
Add to Calendar
2024-10-24 16:00:00
2024-10-24 17:00:00
America/New_York
Hypothesis selection with computational constraints
Abstract: With the ever-growing volume of data, understanding the computational aspects of statistical inference is increasingly critical. A key question arises: Can we develop algorithms that are both fast and memory-efficient to tackle these challenges? In this talk, we focus on the computational aspects of Hypothesis Selection, a fundamental problem in learning theory and statistics. The task is to select a distribution from a finite set of candidate distributions that best matches the underlying distribution of the given dataset. This talk will delve into the hypothesis selection problem under constraints of memory and time. We will explore how to achieve a nearly optimal tradeoff between memory usage and sample complexity, as well as methods to attain optimal accuracy using algorithms with near-optimal time complexity. This talk is based on joint work with Mark Bun and Adam Smith.
G575
October 21
Add to Calendar
2024-10-21 16:00:00
2024-10-21 17:00:00
America/New_York
Almost-Linear Time Algorithms for Partially Dynamic Graphs
Abstract: A partially dynamic graph is a graph that undergoes edge insertions or deletions, but not both. In this talk, I present a unifying framework that resolves numerous well-studied problems on such partially dynamic graphs almost-optimally. These include cycle detection, strongly connected components, s-t distances, transshipment, bipartite matching, maximum flow and minimum-cost flow.We achieve this unification by solving the partially dynamic threshold minimum-cost flow problem. In this problem, one is given a fixed demand vector and a threshold $F$, and tasked with reporting the first time a flow of cost $F$ exists or ceases to exist for insertions and deletions respectively. We give separate algorithms for solving this problem in the incremental and the decremental case. Both follow the L1-IPM framework introduced as part of the first almost linear time minimum-cost flow algorithm [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS'22]. For handling edge insertions, we develop new powerful data structures [Kyng-Meierhans-Probst Gutenberg, STOC'24] to solve the central min-ratio cycle problem against a general adversary [Chen-Kyng-Liu-Meierhans-Probst-Gutenberg, STOC'24]. For handling edge deletions, we take the dual perspective. This leads us to a min-ratio cut problem, which we solve by constructing a dynamic tree that approximately preserves all cuts [van den Brand-Chen-Kyng-Liu-Meierhans-Probst Gutenberg-Sachdevea, FOCS'24].
G575
October 16
Add to Calendar
2024-10-16 16:00:00
2024-10-16 17:00:00
America/New_York
Locally Stationary Distributions: Inference and Optimization Beyond Rapid Mixing
G575
October 09
Proofs of Space with Maximal Hardness
Boston University
Add to Calendar
2024-10-09 16:00:00
2024-10-09 17:00:00
America/New_York
Proofs of Space with Maximal Hardness
In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process.We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space. Our construction is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better security than previously shown.Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every set of $\pi \cdot n$ nodes contains a subset of $\alpha_\pi \cdot n$ nodes whose induced subgraph has just one sink. We take a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.
G575
October 08
Tackling climate change as a research software engineer
University of Cambridge Computer Laboratory
Add to Calendar
2024-10-08 12:00:00
2024-10-08 12:45:00
America/New_York
Tackling climate change as a research software engineer
## Title:Tackling climate change as a research software engineer## Abstract:In this talk I would like to give a high-level overview of the work we carry out in ICCS. How we work with our scientific collaborators to solve research problems and in-house software we have developed to facilitate the addition of ML into legacy weather and climate models. Specifically, we have several groups working with Fortran codes which are now looking to incorporate PyTorch ML models into their existing programs. I also have a keen interest in tooling and I would like to introduce an MPI-aware debugger called mdb, which I am currently developing.## Bio:Tom Meltzer is a senior Research Software Engineer working at the Institute of Computing for Climate Science (ICCS), based at the University of Cambridge. He specializes in high-performance computing, working with scientists to optimize and improve their software to drive better research outcomes. He is currently working on a next generation sea-ice model (NextSimDG), writing a parallel backend using MPI. Before transitioning to research software engineering, he was a atomic and molecular physicist. He obtained his PhD from University College London.
Seminar Room D507
October 02
Add to Calendar
2024-10-02 16:00:00
2024-10-02 17:00:00
America/New_York
Capacity Threshold for the Ising perceptron
Abstract: We show that the capacity of the Ising perceptron is with high probability upper bounded by the constant $\alpha \approx 0.833$ conjectured by Krauth and Mézard, under the condition that an explicit two-variable function $S(\lambda_1,\lambda_2)$ is maximized at (1,0). The earlier work of Ding and Sun proves the matching lower bound subject to a similar numerical condition, and together these results give a conditional proof of the conjecture of Krauth and Mézard.
G575
September 18
Add to Calendar
2024-09-18 16:00:00
2024-09-18 17:00:00
America/New_York
Sparse Graph Counting and Kelley--Meka Bounds for Binary Systems
Abstract: Graph counting lemma of Chung, Graham, and Wilson (Combinatorica 1988) is a fundamental result in combinatorics, which states that if a large graph is pseudorandom, then the number of copies of any small graph $H$ in $G$ is close to what is expected from a random graph of the same density. However, this result is only nontrivial when $G$ is a dense graph. In this work, we obtain a counting lemma that works in the sparse setting, and it is well-suited for the density increment arguments in additive combinatorics. In a recent remarkable breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. We combine our counting lemma with other ideas to establish Kelley--Meka type bounds for all linear patterns defined by translation-invariant systems of binary linear forms, i.e., each form depends on exactly two variables. In particular, we obtain strong bounds for the Turan problem in Abelian Cayley sum graphs, i.e. an upper bound on the maximum edge density of an Abelian Cayley sum graph with a clique of a given size. To prove our results, we employ some of the recent technology developed by Kelley and Meka and also the follow-up work by Kelley, Lovett, and Meka (STOC 2024). This talk is based on a joint work with Yuval Filmus, Hamed Hatami and Kaave Hosseini.
32-G575
September 04
Add to Calendar
2024-09-04 16:00:00
2024-09-04 17:00:00
America/New_York
Towards Bridging Causal Inference and Algorithmic Decision-Making
Abstract: The goal in causal inference is to estimate counterfactual outcomes of units (e.g. patients, customers, subpopulations) under different interventions (e.g. medical treatments, discounts, socioeconomic policies). However, the end goal in practice is often to use these counterfactual estimates to make a decision which optimizes some downstream objective (e.g., maximizing life expectancy or revenue, minimizing unemployment). To bridge counterfactual estimation and decision-making, there are additional challenges one must take into account. We study two such challenges: (i) interventions are applied adaptively using some learning algorithm, (ii) units are strategic in what data they share about themselves. Specifically, we focus on the setting of panel data, where a learner observes repeated, noisy measurements of units over time. This talk is based on the following papers: https://arxiv.org/pdf/2307.01357 (NeurIPS 2023) and https://arxiv.org/pdf/2312.16307 (preprint).
32-G575
August 19
Exascale Climate Emulators: Enhancing Earth System Model Outputs and Reducing Petabytes of Storage
Sameh Abdulah
King Abdullah University of Science and Technology
Add to Calendar
2024-08-19 14:00:00
2024-08-19 15:00:00
America/New_York
Exascale Climate Emulators: Enhancing Earth System Model Outputs and Reducing Petabytes of Storage
Title:Exascale Climate Emulators: Enhancing Earth System Model Outputs and Reducing Petabytes of Storage Abstract:We present an exascale climate emulator to tackle the rising computational and storage demands of high-resolution Earth System Model simulations. Using spherical harmonic transform, we model spatio-temporal climate variations stochastically, providing tunable resolution and significantly enhancing emulation fidelity. We extend linear solver software to multi-precision arithmetic GPUs, adapting to different correlation strengths. The PaRSEC runtime system optimizes parallel matrix operations by balancing computation, communication, and memory. Our BLAS3-rich code is optimized for diverse GPU systems, achieving 0.523 EFlops/s on 4,096 ORNL Frontier nodes (projected 1.04 EFlops/s on 8,192 nodes), 0.243 EFlops/s on 1,024 Cineca Leonardo nodes, and 0.375 EFlops/s on 3,072 ORNL Summit nodes. Bio:Sameh Abdulah obtained his MS and Ph.D. degrees from Ohio State University, Columbus, USA, in 2014 and 2016, respectively. Presently, he serves as a research scientist at the Extreme Computing Research Center (ECRC), King Abdullah University of Science and Technology, Saudi Arabia. His research focuses on various areas, including high-performance computing applications, big data, bitmap indexing, handling large spatial datasets, parallel spatial statistics applications, algorithm-based fault tolerance, and machine learning and data mining algorithms. Sameh was a part of the KAUST team nominated for the ACM Gordon Bell Prize in 2022 for their work on large-scale climate/weather modeling and prediction.
Seminar Room G449 (Patil/Kiva)