Add to Calendar2024-09-20 10:30:002024-09-20 12:00:00America/New_YorkLali Devadas, Batching Adaptively-Sound SNARGs for NPA succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement is true with a proof whose size is sublinear in the length of its NP witness. Moreover, a SNARG is adaptively sound if the adversary can choose the statement it wants to prove after seeing the scheme's public parameters. Recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-exponentially secure indistinguishability obfuscation, sub-exponentially secure one-way functions, and polynomial hardness of the discrete log assumption).We consider the batch setting where the prover wants to certify a collection of statements and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of statements. All existing adaptively-sound constructions either require the size of the public parameters to scale linearly with the number of statements or have proof size that scales linearly with the size of a single NP witness. In this work, we show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we can obtain an adaptively-sound SNARG for batch-NP where the size of the proof is poly(k) and the size of the public parameters is poly(k+|C|), where k is a security parameter and |C| is the size of the circuit that computes the associated NP relation.We give two approaches for batching adaptively-sound SNARGs for NP. Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) and avoids relying on a structure like homomorphism.Joint work with Brent Waters (UT Austin and NTT Research) and David J. Wu (UT Austin).32-G882 Hewlett
Add to Calendar2024-09-23 14:00:002024-09-23 15:00:00America/New_YorkRoblox Tech Talk at CSAIL featuring Chief Scientist and MIT alumnus Morgan McGuireYou’re invited for an exclusive look into Roblox directly from our Chief Scientist Morgan McGuire! Join us as he discusses the technical vision and direction of Roblox. You’ll have the opportunity to hear firsthand about the challenges and successes that have shaped Roblox for decades as well as a live Q&A. Recruiters and previous CSAIL interns at Roblox will be there to speak with interested students. September 23, 20242-3 PM ESTHewlett Seminar Room (Room 32-G882 in CSAIL/STATA)
Add to Calendar2024-09-24 14:00:002024-09-24 15:00:00America/New_YorkByte Bites with Andreea BobuTitle: Aligning Robot and Human RepresentationsAbstract: To perform tasks that humans want in the world, robots rely on a representation of salient task features; for example, to hand me a cup of coffee, the robot considers features like efficiency and cup orientation in its behavior. Prior methods try to learn both a representation and a downstream task jointly from data sets of human behavior, but this unfortunately picks up on spurious correlations and results in behaviors that do not generalize. In Andreea's view, what’s holding us back from successful human-robot interaction is that human and robot representations are often misaligned: for example, our assistive robot moved a cup inches away from my face -- which is technically collision-free behavior -- because it lacked an understanding of personal space. Instead of treating people as static data sources, Andreea's key insight is that robots must engage with humans in an interactive process for finding a shared representation for more efficient, transparent, and seamless downstream learning. In this talk, Andreea focuses on a divide and conquer approach: explicitly focus human input on teaching robots good representations before using them for learning downstream tasks. This means that instead of relying on inputs designed to teach the representation implicitly, we have the opportunity to design human input that is explicitly targeted at teaching the representation and can do so efficiently. Andreea introduces a new type of representation-specific input that lets the human teach new features, enables robots to reason about the uncertainty in their current representation and automatically detect misalignment, and proposes a novel human behavior model to learn robust behaviors on top of human-aligned representations. By explicitly tackling representation alignment, Andreea believe we can ultimately achieve seamless interaction with humans where each agent truly grasps why the other behaves the way they do.
Add to Calendar2024-09-24 16:00:002024-09-24 17:00:00America/New_YorkHCI Seminar - Lane Harrison - Shaping Visualization Ecosystems in a Changing Technosocial LandscapeAbstract:Progress across visualization systems, data journalism, and social media has brought charts and interactives into peoples’ daily lives. But this progress brings new challenges: How do people engage with visualizations they encounter? How might people differ in their ability to read and use visualizations, and can these skills be improved? Do visualization tools and creators favor audiences with particular social or cultural characteristics over others? This talk will cover research initiatives that interrogate these challenges through experiments and design, and propose how we might anticipate and respond to coming shifts in visualization ecosystems.Bio:Lane Harrison is an Associate Professor in the Department of Computer Science at Worcester Polytechnic Institute. Before joining WPI, Lane was a postdoctoral fellow in the Department of Computer Science at Tufts University. Lane directs the Visualization and Information Equity lab at WPI (VIEW), where he and students leverage computational methods to understand and shape how people engage with data visualizations and visual analytics systems. Lane’s work has been supported by the NSF, DoED, DoD, and industry.This talk will also be streamed over Zoom: https://mit.zoom.us/j/9199160886132-G882 (Hewlett)
Add to Calendar2024-09-24 16:15:002024-09-24 17:15:00America/New_YorkNear Optimal Alphabet-Soundness Tradeoff PCPsRefreshments at 4:00 PMAbstract: We show a nearly optimal alphabet-soundness tradeoff for NP-hardness of 2-Prover-1-Round Games (2P1R). More specifically, we show that for all \eps > 0, for sufficiently large M, it is NP-hard to decide whether a 2P1R instance of alphabet size M has value nearly 1 or at most M^{-1+\eps}. 2P1R are equivalent to 2-Query PCP, and are widely used in obtaining hardness of approximation results. As such, our result implies the following: 1) hardness of approximating Quadratic Programming within a factor of nearly log(n), 2) hardness of approximating d-bounded degree 2-CSP within a factor of nearly d/2, and 3) improved hardness of approximation results for various k-vertex connectivity problems. For the first two applications, our results nearly match the performance of the best known algorithms.Joint work with Dor Minzer.32-G449
Add to Calendar2024-09-25 11:30:002024-09-25 13:00:00America/New_YorkProf. Ard Louis: Does evolution have an inbuilt bias towards highly compressible phenotypes?This is a virtual seminar - please join using the Zoom link below!Zoom: https://harvard.zoom.us/j/99103715484
Add to Calendar2024-09-26 15:00:002024-09-26 17:30:00America/New_YorkBounded Arithmetic Reading GroupBounded arithmetic is a collective name of fragments of Peano arithmetic that are closely related to complexity classes, such as P, PH, and L. The study of bounded theories is relevant to the program of showing unprovability of complexity conjectures; moreover, the techniques in this field are found useful in complexity theory and cryptography. In this reading group, we will learn basics of bounded arithmetic from scratch (without assuming backgrounds in logic).Organizer: Jiatu LiSeminar Room G575
32-G449 (Stata Center, Patil-Kiva Conference Room)
Add to Calendar2024-09-26 16:00:002024-09-26 17:00:00America/New_YorkLearning Robust, Real-world Visuomotor Skills from Generated DataAbstract: The mainstream approach in robot learning today relies heavily on imitation learning from real-world human demonstrations. These methods are sample efficient in controlled environments and easy to scale to a large number of skills. However, I will present algorithmic arguments to explain why merely scaling up imitation learning is insufficient for advancing robotics. Instead, my talk will focus on developing performant visuomotor policies in simulation and the techniques that make them robust enough to transfer directly to real-world color observations.I will introduce LucidSim, our recent breakthrough in producing real-world perceptive robot policies from synthetic data. Using only generated images, we successfully trained a robot dog to perform parkour through obstacles at high speed, relying solely on a color camera for visual input. I will discuss how we generate diverse and physically accurate image sequences within simulated environments for learning, and address the system challenges we overcame to scale up. Finally, I will outline our push for versatility and plans to acquire three hundred language-aware visuomotor skills by the end of this year. These are the first steps toward developing fully autonomous, embodied agents that require deeper levels of intelligence.Bio: Ge Yang is a postdoctoral researcher working with Phillip Isola at MIT CSAIL. His research focuses on developing the algorithmic and system foundations for computational visuomotor learning, with an emphasis on learning from synthetic data and sim-to-real transfer. Ge's work is dedicated to making robots capable, versatile, and intelligent.Before transitioning into AI and robotics, Ge earned his Ph.D. in Physics from the University of Chicago and a Bachelor of Science in Mathematics and Physics from Yale University. His experience in physics motivated a multidisciplinary approach to problem-solving in AI. He is a recipient of the NSF Institute of AI and Fundamental Interactions Postdoc Fellowship and the Best Paper Award at the 2024 Conference on Robot Learning (CoRL), selected from 499 submissions.32-G449 (Stata Center, Patil-Kiva Conference Room)
Add to Calendar2024-09-27 10:30:002024-09-27 12:00:00America/New_YorkSeyoon Ragavan: Indistinguishability Obfuscation from Bilinear Maps and LPN VariantsWe construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$. As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024). Joint work with Neekon Vafa (MIT) and Vinod Vaikuntanathan (MIT).32-G882 Hewlett
Add to Calendar2024-10-08 12:00:002024-10-08 12:45:00America/New_YorkTackling 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.
Add to Calendar2024-10-08 12:45:002024-10-08 13:30:00America/New_YorkML approaches to accelerate the spin-up phase of climate models: A software engineering perspective.## Title:ML approaches to accelerate the spin-up phase of climate models: A software engineering perspective.## Abstract:The ICCS collaborates with two VESRI sites (M2Lines and CALIPSO) toward accelerating the spin-up phase of climate models using data driven methods. The term 'spin-up' is the process by which traditional climate models reach equilibrium; a necessary step to run a numerical experiment forwards in time. This process, be it a land surface model or ocean model, and a set of initial conditions, can take up to 98% of the running time of a typical model experiment, which may consume months of computing resources on a supercomputer. This is a major bottleneck in integrating ever increasing observational data (a big model - big data dilemma). Recently, climate researchers have identified various ways to use data-driven machine learning based acceleration tools (MLA) to reduce the computational demand of traditional spin-up methods. In this talk, we will give an overview of the SPINAcc and Spinup-NEMO projects from a software engineering perspective, focusing on the project redesign and refactoring that ICCS engineers are currently undertaking, as well efforts towards optimising the spin-up acceleration tool which maximises the computational time savings and minimises biases in the ML predictions.===========## Bio:Matthew Archer is a senior research software engineer in the ICCS based at the University of Cambridge. He currently specialises in machine learning for climate science applications and is generally interested in the accelerated spin-up of climate models using data driven techniques. He previously contributed to the development of the finite element software library FEniCS, after completing a PhD in Computational Physics from the same university specialising in Solid Mechanics.Seminar Room G449 (Patil/Kiva)
Add to Calendar2024-10-10 15:00:002024-10-10 17:00:00America/New_YorkBounded Arithmetic Reading GroupBounded arithmetic is a collective name of fragments of Peano arithmetic that are closely related to complexity classes, such as P, PH, and L. The study of bounded theories is relevant to the program of showing unprovability of complexity conjectures; moreover, the techniques in this field are found useful in complexity theory and cryptography. In this reading group, we will learn basics of bounded arithmetic from scratch (without assuming backgrounds in logic).Organizer: Jiatu LiSeminar Room G575
Add to Calendar2024-10-17 15:00:002024-10-17 17:30:00America/New_YorkBounded Arithmetic Reading GroupBounded arithmetic is a collective name of fragments of Peano arithmetic that are closely related to complexity classes, such as P, PH, and L. The study of bounded theories is relevant to the program of showing unprovability of complexity conjectures; moreover, the techniques in this field are found useful in complexity theory and cryptography. In this reading group, we will learn basics of bounded arithmetic from scratch (without assuming backgrounds in logic).Organizer: Jiatu LiSeminar Room G575
Add to Calendar2024-11-01 14:00:002024-11-01 16:30:00America/New_YorkSecurity SeminarProgram:2:00pm - 3:00pmTECHNOLOGY REVOLUTIONSMikko Hypponen, WithSecureAbstract:All new technical innovations come with both advantages and disadvantages; we cannot simply select the benefits without also encountering the challenges. Once something is invented, we can't make it go away. This applies to things like artificial intelligence, the Tor Network, cryptocurrencies, strong encryption, quantum computing - even the internet itself.Mikko Hypponen is one of the most recognized cyber security experts world-wide, a keynote speaker and a best-selling author. Mikko works as the Chief Research Officer for WithSecure in Finland. He has served as an advisor for EUROPOL and the Monetary Authority of Singapore. Mikko's TED Talk has been seen by 2 million people, and his latest book has been translated to 5 languages.3:00pm - 3:30pm - Coffee Break3:30pm - 4:30pmA Voting Machine Everyone Can TrustBen Adida, VotingWorks.SB '98, MEng '99, PhD '06 Abstract:What does it take to build a voting machine that every voter can trust? Over the last 5 years, at VotingWorks, we've been working in the open on exactly that problem. We've concluded that the broadly accepted expert recommendations – paper ballots and post-election audits – are certainly necessary but far from sufficient. With public scrutiny into voting systems at an all-time high, and confidence in the outcome of our elections becoming increasingly partisan, we propose a new standard for voting machines – a standard that includes real transparency, strong system integrity, and a focus on simplicity. In this talk, we'll cover the why and the how, and we'll have voting equipment for attendees to try.32-155