Add to Calendar
2024-05-08 10:00:00
2024-05-08 11:30:00
America/New_York
Thesis Defense: Shyan Akmal: Parameterized Relaxations for Circuits and Graphs
Abstract:What makes some problems hard to solve, and others easy? In situations where complexity-theoretic hypotheses rule out the possibility of fast algorithms for problems, are there nonetheless instances for which we can “evade intractability” and still design efficient algorithms? In this thesis, we investigate these questions from the perspective of parameterized relaxations. We investigate computational problems on circuits and graphs, and design fast algorithms for relaxed versions of these tasks, thereby identifying tractable instances of problems which are provably hard in general. In this talk, we focus on parameterized relaxations for Majority-SAT, a problem on circuits, and All-Pairs Connectivity, a problem on graphs.Majority-SAT is the problem of determining whether a given n-variable formula has at least 2^{n-1} satisfying assignments. Majority-SAT has been studied extensively in computer science communities interested in the complexity of probabilistic planning and inference. Although this problem has been known to be PP-complete for fifty years, the complexity of a natural variant remained open: Majority-kSAT, where the input is a formula in conjunctive normal form with clause width at most k (i.e., the input is a k-CNF formula). In work with Ryan Williams, we resolve this open problem, and determine the complexity of Majority-kSAT for all constant k.All-Pairs Connectivity (APC) is the problem of computing the maximum flow from s to t for all pairs of nodes (s,t) in a given unweighted graph. Although APC can be solved in optimal near-quadratic time over undirected graphs, in general directed graphs it is known that APC cannot be solved in truly subcubic time assuming the Strong Exponential Time Hypothesis. Consequently, on directed graphs researchers have studied a variant of APC: k-APC, where we are given a positive integer k, and must return the maximum flow from s to t only for pairs of nodes (s,t) with maximum flow value less than k (i.e., return all “small maximum flow values”). Despite significant research in flow problems, it was an open question to determine whether k-APC could be solved faster than the general APC problem even for k=3. In work with Ce Jin, we resolve this open problem, and determine the optimal time complexity for solving k-APC for all constant k (up to conjectures in fine-grained complexity).
G882 Hewlett
Events
May 08, 2024
A Biased Introduction to Average-Case Fine Grained Complexity
Boston University
Add to Calendar
2024-05-08 16:00:00
2024-05-08 17:00:00
America/New_York
A Biased Introduction to Average-Case Fine Grained Complexity
Abstract: I will introduce the techniques and approaches of fine-grained average-case complexity. I will explain the centrality of low degree polynomials. I will highlight results from many papers and different techniques that can be used. We will end with a result showing that for any constant sized subgraph H, counting the number of H in a worst-case graph and counting the number of H in an Erdős–Rényi graph take the same time up to polylog factors.
32-G575
May 09, 2024
THESIS DEFENSE: On Physics-Inspired Generative Models
Yilun Xu
MIT-CSAIL
Add to Calendar
2024-05-09 17:00:00
2024-05-09 18:00:00
America/New_York
THESIS DEFENSE: On Physics-Inspired Generative Models
Abstract: Physics-inspired generative models such as diffusion models constitute a powerful family of generative models. The advantages of models in this family come from relatively stable training process and high capacity. A number of possible improvements remain possible. In this talk, I will discuss the enhancement and design of physics-inspired generative models. I will first present a sampling algorithm that combines the best of previous samplers, greatly accelerating the generation speed of text-to-image Stable Diffusion models. Secondly, I will discuss a training framework that introduces learnable discrete latents into continuous diffusion models. These latents simplify complex noise-to-data mappings and reduce the curvature of generative trajectories. Finally, I will introduce Poisson Flow Generative Models (PFGM), a new generative model arising from electrostatic theory, rivaling leading diffusion models. The extended version, PFGM++, places diffusion models and PFGM under the same framework and introduces new, better models. Several algorithms discussed in the talk are the state-of-the-art methods across standard benchmarks. Committee Members: Tommi Jaakkola (advisor, MIT), Phillip Isola (MIT), Karsten Kreis (NVIDIA)
32-D463 (Star). Zoom Link: https://mit.zoom.us/j/8869131067
May 09, 2024
THESIS DEFENSE: On Physics-Inspired Generative Models
Yilun Xu
MIT-CSAIL
Add to Calendar
2024-05-09 17:00:00
2024-05-09 18:00:00
America/New_York
THESIS DEFENSE: On Physics-Inspired Generative Models
Abstract: Physics-inspired generative models such as diffusion models constitute a powerful family of generative models. The advantages of models in this family come from relatively stable training process and high capacity. A number of possible improvements remain possible. In this talk, I will discuss the enhancement and design of physics-inspired generative models. I will first present a sampling algorithm that combines the best of previous samplers, greatly accelerating the generation speed of text-to-image Stable Diffusion models. Secondly, I will discuss a training framework that introduces learnable discrete latents into continuous diffusion models. These latents simplify complex noise-to-data mappings and reduce the curvature of generative trajectories. Finally, I will introduce Poisson Flow Generative Models (PFGM), a new generative model arising from electrostatic theory, rivaling leading diffusion models. The extended version, PFGM++, places diffusion models and PFGM under the same framework and introduces new, better models. Several algorithms discussed in the talk are the state-of-the-art methods across standard benchmarks. Committee Members: Tommi Jaakkola (advisor, MIT), Phillip Isola (MIT), Karsten Kreis (NVIDIA)
32-D463 (Star). Zoom Link: https://mit.zoom.us/j/8869131067
May 10, 2024
Pseudorandom Error-Correcting Codes
Miranda Christ (Columbia University)
Add to Calendar
2024-05-10 10:30:00
2024-05-10 12:00:00
America/New_York
Pseudorandom Error-Correcting Codes
We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key.We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either 2^{O(\sqrt{n})}-hardness of LPN, or polynomial hardness of LPN and the planted XOR problem at low density.As our primary application of pseudorandom codes, we present an undetectable watermarking scheme for outputs of language models that is robust to cropping and a constant rate of random substitutions and deletions. The watermark is undetectable in the sense that any number of samples of watermarked text are computationally indistinguishable from text output by the original model. This is the first undetectable watermarking scheme that can tolerate a constant rate of errors.Our second application is to steganography, where a secret message is hidden in innocent-looking content. We present a constant-rate stateless steganography scheme with robustness to a constant rate of substitutions. Ours is the first stateless steganography scheme with provable steganographic security and any robustness to errors.This is based on joint work with Sam Gunn: https://eprint.iacr.org/2024/235
32-G882 Hewlett Room
May 14, 2024
Low-Step Multi-Commodity Flow Emulators
Thatchaphol Saranurak
University of Michigan
Add to Calendar
2024-05-14 16:15:00
2024-05-14 17:15:00
America/New_York
Low-Step Multi-Commodity Flow Emulators
Abstract: We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.We prove the existence of low-step multi-commodity flow emulators and develop efficient algorithms to compute them. We then apply them to solve constant-approximate $k$-commodity flow in $O((m+k)^{1+\epsilon})$ time. To bypass the $O(mk)$ flow decomposition barrier, we represent our output multi-commodity flow implicitly; prior to our work, even the existence of implicit constant-approximate multi-commodity flows of size $o(mk)$ was unknown.Our results generalize to the \emph{minimum cost} setting, where each edge has an associated cost and the multi-commodity flow must satisfy a cost budget. Our algorithms are also parallel.
32-G449
May 17, 2024
Zhengzhong Jin: Universal SNARGs for NP from Proofs of Completeness
Zhengzhong Jin (Northeastern University)
Add to Calendar
2024-05-17 10:30:00
2024-05-17 12:00:00
America/New_York
Zhengzhong Jin: Universal SNARGs for NP from Proofs of Completeness
We construct a succinct non-interactive argument system (SNARG) for any NP language L, and prove the non-adaptive soundness assuming the security of an FHE scheme, a batch argument (BARG) scheme, as well as the existence of any two-message argument system for L that has a polynomial-size Extended Frege proof of the completeness property. Our SNARG is *universal* in the sense that the construction does not depend on the two-message argument system.We also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness.Our framework yields several corollaries, including:- a SNARG for NP with a transparent CRS and non-adaptive soundness, assuming LWE and the (non-explicit) existence of any witness encryption for NP that has a polynomial-size 'Extended Frege proof of correctness'. As a corollary, we obtain SNARGs for NP under the evasive LWE and subexponential LWE assumptions, with a (long) transparent CRS and non-adaptive soundness. - a SNARG for UP with a long (and even transparent!) CRS and adaptive soundness under the evasive LWE and subexponential LWE assumptions.- a SNARG for NP with a short CRS and non-adaptive soundness assuming LWE, FHE, and the (non-explicit) existence of any hash function that makes Micali's SNARG construction sound.We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a ``best possible SNARG''.Based on the joint work with Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan.
32-G882 (Hewlett)
May 24, 2024
Dynamic Adaptive Optimization: Recovering from Hardware Errors and Software Crashes in a Distributed Virtual Machine
University of California, Santa Cruz
Add to Calendar
2024-05-24 14:00:00
2024-05-24 15:00:00
America/New_York
Dynamic Adaptive Optimization: Recovering from Hardware Errors and Software Crashes in a Distributed Virtual Machine
Abstract: TidalScale was a startup aquired by HPE in December 2022. TidalSale developed a software architecture called distributed virtual machines. Today's virtual machines in widespread use today allows multiple operating systems to share a server. TidalScale inverts this paradigm. A single virtual machine running on TidalScale runs a single operating system instance across a cluster of standard servers. This virtual machine sits between an operating system and a cluster of servers. It runs on premise or in the cloud. Because they are virtual, resources like processors and memory can migrate among nodes in the cluster. The virtual machine dynamically self-optimizes resource placement in real time under contol of a set of machine learning algorithms. Servers can automatically and dynamically be added and removed depending on fluctuationg workloads, allowing for dynamic hardware scalability, but also increasing reliability and resiliency. In this talk, we specifically show how these servers automatically, without any human intervention, recover from most hardware failures, and and provide excellent restart performance should OS failures occur.Bio: Ike Nassi is a consultant and an Adjunct Professor of Computer Science at UC Santa Cruz, a Founding Trustee at the Computer History Museum and an advisory board member of TTI/Vanguard. Ike was the founder of TidalScale, sold to HPE Dec. 2022. Previously, he was an Executive Vice President and Chief Scientist at SAP. Ike started or helped to start four companies: Encore Computer Corporation building hierarchical strongly coherent shared memory symmetric multiprocessors (1984); InfoGear Technology, which developed both Internet appliances (including the first iPhone) (1996); Firetide, an early wireless mesh networking company (2000), and TidalScale (2012). He was SVP for Software at Apple Computer and a Corporate Officer. He worked at Visual Technology, and Digital Equipment Corporation. In the past, Dr. Nassi was a Visiting Scholar at Stanford University, twice a Research Scientist at MIT, and a Visiting Scholar at University of California, Berkeley. He has served on the board of the Anita Borg Institute for Women and Technology, and the IEEE Computer Society Industry Advisory Board. He holds a PhD in Computer Science from Stony Brook University.He was awarded two certificates for Distinguished Service from the Department of Defense, one for his work on the design of the programming language Ada and one for his work on DARPA ISAT. He is a Life Fellow of IEEE and a Life member of ACM. He is named on over 35 patents.
32-G575
June 07, 2024
Add to Calendar
2024-06-07 9:00:00
2024-06-07 18:00:00
America/New_York
CSAIL + Imagination in Action Symposium 2024
The symposium will showcase the extraordinary and substantive contributions CSAIL research groups have made, and highlight the remarkable impacts of our work.
Kirsch Auditorium
December 01, 2024
Cancelled
Test event
This event has been cancelled