Start Date: 19 Feb 2024; Start Time: 10:30AM - 12:00PM Title: Modern Algorithms for Massive Graphs: Structure and Compression Bio: Zihan Tan is a postdoctoral associate at DIMACS, Rutgers University. Before joining DIMACS, he obtained his Ph.D. from the University of Chicago, where he was advised by Julia Chuzhoy. He is broadly interested in theoretical computer science, with a focus on graph algorithms and graph theory. Speaker: Abstract: In the era of big data, the significant growth in graph size renders numerous traditional algorithms, including those with polynomial or even linear time complexity, inefficient. Therefore, we need novel approaches for efficiently processing massive graphs. In this talk, I will discuss two modern approaches towards this goal: structure exploitation and graph compression. I will first show how to utilize graph structure to design better approximation algorithms, showcasing my work on the Graph Crossing Number problem. I will then show how to compress massive graphs into smaller ones while preserving their flow/cut/distance structures and thereby obtaining faster algorithms. Location: CoRE 301 Committee: |
Start Date: 20 Feb 2024; Start Time: 10:30AM - 12:00PM Title: The Computational Cost of Detecting Hidden Structures: from Random to Deterministic Bio: Tim Kunisky is a postdoctoral associate at Yale University, hosted by Dan Spielman in the Department of Computer Science. He previously graduated with a bachelor’s degree in mathematics from Princeton University, worked on machine learning for ranking problems and natural language processing at Google, and received his PhD in Mathematics from the Courant Institute of Mathematical Sciences at New York University, where he was advised by Afonso Bandeira and Gérard Ben Arous. His main research interests concern how probability theory and mathematical statistics interact with computational complexity and the theory of algorithms. Speaker: Abstract: I will present a line of work on the computational complexity of algorithmic tasks on random inputs, including hypothesis testing, sampling, and certifying bounds on optimization problems. Surprisingly, these diverse tasks admit a unified analysis involving the same two main ingredients. The first is the study of algorithms that output low-degree polynomial functions of their inputs. Such algorithms are believed to be optimal for many statistical tasks and can be understood with the theory of orthogonal polynomials, leading to strong evidence for the difficulty of certain hypothesis testing problems. The second is a strategy of "planting" unusual structures in problem instances, which shows that algorithms for sampling and certification can be interpreted as implicitly performing hypothesis testing. I will focus on examples of hypothesis testing related to principal component analysis (PCA), and their connections with problems motivated by statistical physics: (1) sampling from Ising models, and (2) certifying bounds on random functions associated with models of spin glasses.Next, I will describe more recent results probing the computational cost of certification not just in random settings under strong distributional assumptions, but also for more generic problem instances. As an extreme example, by considering the sum-of-squares hierarchy of semidefinite programs, I will show how some of the above ideas may be completely derandomized and applied in a deterministic setting. Using as a testbed the long-standing open problem of computing the clique number of the number-theoretic Paley graph, I will give an analysis of semidefinite programming that leads both to new approaches to this combinatorial optimization problem and to refined notions of pseudorandomness capturing deterministic versions of phenomena from random matrix theory and free probability. Location: CoRE 301 Committee: |
Start Date: 22 Feb 2024; Start Time: 10:30AM - 12:00PM Title: Economics Meets Approximations Bio: Kangning Wang is currently a Motwani Postdoctoral Fellow at Stanford University. He earned his Ph.D. from Duke University in 2022 and subsequently held the position of J.P. Morgan Research Fellow at the Simons Institute at UC Berkeley. Kangning's research is at the interface of computer science, economics, and operations research, with a focus on developing economic and societal solutions from an algorithmic perspective. His research has been recognized by an ACM SIGecom Doctoral Dissertation Award Honorable Mention, a Duke CS Best Dissertation Award, and Best Paper Awards at SODA 2024 and WINE 2018. Speaker: Abstract: Traditional economic research often focuses on solutions that are exactly optimal. However, these exact optima frequently prove undesirable, due to concerns surrounding incentives, robustness, fairness, computational efficiency, and more. This has led to the formulation of several renowned "impossibility theorems." More recently, the emerging interdisciplinary field of *economics and computation* has brought about a shift in perspective, embracing an approximation-based approach to classical problems. This shift opens up avenues for novel economic solutions that both hold theoretical significance and provide practical guidelines to complex real-world applications. In this presentation, I will explore this approximation viewpoint applied to various well-established economic concepts, highlighting its power of uncovering the once-impossible possibilities. Location: CoRE 301 Committee: |
Start Date: 22 Feb 2024; Start Time: 02:00PM - 04:00PM Title: Hybrid CPU-GPU Architectures for Processing Large-Scale Data on Limited Hardware Bio: Speaker: Abstract: In the dynamic field of data processing, efficiently managing large-scale data, both offline and in real-time, is a growing challenge. With the limitations of hardware as a focal concern, this dissertation introduces hybrid CPU-GPU frameworks. These are designed specifically to meet the computational needs of data-intensive environments in real time. A central feature of these designs is a unique shared-memory-space approach, which is effective in facilitating data transfers and ensuring synchronization across multiple computations. The research highlights the increasing trend towards swift processing of large-scale data. In sectors like distributed fiber optic sensing, there's a consistent demand for immediate real-time data processing. These designs combine the advantages of both CPU and GPU components, effectively handling fluctuating workloads and addressing computational challenges. Designed for optimal performance in diverse computing environments with limited hardware, the system architecture offers scalability, adaptability, and increased efficiency. Key components of the design, such as shared memory space utilization, process replication, CPU-GPU synchronization, and real-time visualization capabilities, are thoroughly analyzed to demonstrate its capability in real-time data processing. Location: CoRE 301 Committee: Prof. Badri Nath (Chair) Prof. Srinivas Narayana Prof. Zheng Zhang Prof. Kazem Cheshmi (External) |
Start Date: 23 Feb 2024; Start Time: 10:30AM - 12:00PM Title: Fundamental Problems in AI: Transferability, Compressibility and Generalization Bio: Tomer Galanti is a Postdoctoral Associate at the Center for Brains, Minds, and Machines at MIT, where he focuses on the theoretical and algorithmic aspects of deep learning. He received his Ph.D. in Computer Science from Tel Aviv University, during which he served as a Research Scientist Intern at Google DeepMind's Foundations team. He has published numerous papers in top-tier conferences and journals, including NeurIPS, ICML, ICLR, and JMLR. Notably, his paper "On the Modularity of Hypernetworks" was awarded an oral presentation at NeurIPS 2020. Speaker: Abstract: In this talk, we delve into several fundamental questions in deep learning. We start by addressing the question, "What are good representations of data?" Recent studies have shown that the representations learned by a single classifier over multiple classes can be easily adapted to new classes with very few samples. We offer a compelling explanation for this behavior by drawing a relationship between transferability and an emergent property known as neural collapse. Later, we explore why certain architectures, such as convolutional networks, outperform fully-connected networks, providing theoretical support for how their inherent sparsity aids learning with fewer samples. Lastly, I present recent findings on how training hyperparameters implicitly control the ranks of weight matrices, consequently affecting the model's compressibility and the dimensionality of the learned features.Additionally, I will describe how this research integrates into a broader research program where I aim to develop realistic models of contemporary learning settings to guide practices in deep learning and artificial intelligence. Utilizing both theory and experiments, I study fundamental questions in the field of deep learning, including why certain architectural choices improve performance or convergence rates, when transfer learning and self-supervised learning work, and what kinds of data representations are learned in practical settings. Location: CoRE 301 Committee: |
Start Date: 26 Feb 2024; Start Time: 10:30AM - 12:00PM Title: The Marriage of (provable) Algorithm Design and Machine Learning Bio: Sandeep is a final year PhD student at MIT, advised by Piotr Indyk. His interests are broadly in fast algorithm design. Recently, he has been working in the intersection of machine learning and classical algorithms by designing provable algorithms in various ML settings, such as efficient algorithms for processing large datasets, as well as using ML to inspire algorithm design. Speaker: Abstract: The talk is motivated by two questions at the interplay between algorithm design and machine learning: (1) How can we leverage the predictive power of machine learning in algorithm design? and (2) How can algorithms alleviate the computational demands of modern machine learning?Towards the first question, I will demonstrate the power of data-driven and learning-augmented algorithm design. I will argue that data should be a central component in the algorithm design process itself. Indeed in many instances, inputs are similar across different algorithm executions. Thus, we can hope to extract information from past inputs or other learned information to improve future performance. Towards this end, I will zoom in on a fruitful template for incorporating learning into algorithm design and highlight a success story in designing space efficient data structures for processing large data streams. I hope to convey that learning-augmented algorithm design should be a tool in every algorithmist's toolkit.Then I will discuss algorithms for scalable ML computations to address the second question. I will focus on my works in understanding global similarity relationships in large high-dimensional datasets, encoded in a similarity matrix. By exploiting geometric structure of specific similarity functions, such as distance or kernel functions, we can understand the capabilities -- and fundamental limitations -- of computing on similarity matrices. Overall, my main message is that sublinear algorithms design principles are instrumental in designing scalable algorithms for big data. I will conclude with some exciting directions in pushing the boundaries of learning-augmented algorithms, as well as new algorithmic challenges in scalable computations for faster ML. Location: CoRE 301 Committee: |
Start Date: 27 Feb 2024; Start Time: 10:30AM - 12:00PM Title: A Step Further Toward Scalable and Automatic Distributed Large Language Model Pre-training Bio: Hongyi Wang is a Senior Project Scientist at the Machine Learning Department of CMU working with Prof. Eric Xing. He obtained his Ph.D. degree from the Department of Computer Sciences at the University of Wisconsin-Madison, where he was advised by Prof. Dimitris Papailiopoulos. Dr. Wang received the Rising Stars Award from the Conference on Parsimony and Learning in 2024 and the Baidu Best Paper Award at the Spicy FL workshop at NeurIPS 2020. He led the distributed training effort of LLM360, an academic research initiative advocating for fully transparent open-source LLMs. His research has been adopted by companies like IBM, Sony, and FedML Inc., and he is currently funded by NSF, DARPA, and Semiconductor Research Corporation. Speaker: Abstract: Large Language Models (LLMs), such as GPT and LLaMA, are at the forefront of advances in the field of AI. Nonetheless, training these models is computationally daunting, necessitating distributed training methods. Distributed training, however, generally suffers from bottlenecks like heavy communication costs and the need for extensive performance tuning. In this talk, I will first introduce a low-rank training framework for enhancing communication efficiency in data parallelism. The proposed framework achieves almost linear scalability without sacrificing model quality, by leveraging a full-rank to low-rank training strategy and a layer-wise adaptive rank selection mechanism. Hybrid parallelism, which combines data and model parallelism, is essential for LLM pre-training. However, designing effective hybrid parallelism strategies requires heavy tuning effort and strong expertise. I will discuss how to automatically design high-throughput hybrid-parallelism training strategies using system cost models. Finally, I will demonstrate how to use the automatically designed hybrid parallelism strategies to train state-of-the-art LLMs. Location: CoRE 301 Committee: |
Start Date: 29 Feb 2024; Start Time: 10:30AM - 12:00PM Title: Bridging the Gap Between Theory and Practice: Solving Intractable Problems in a Multi-Agent Machine Learning World Bio: Emmanouil-Vasileios (Manolis) Vlatakis Gkaragkounis is currently a Foundations of Data Science Institute (FODSI) Postdoctoral Fellow at the Simons Institute for the Theory of Computing, UC Berkeley, mentored by Prof. Michael Jordan. He completed his Ph.D. in Computer Science at Columbia University, under the guidance of Professors Mihalis Yannakakis and Rocco Servedio, and holds B.Sc. and M.Sc. degrees in Electrical and Computer Engineering. Manolis specializes in the theoretical aspects of Data Science, Machine Learning, and Game Theory, with expertise in beyond worst-case analysis, optimization, and data-driven decision-making in complex environments. His work has applications across multiple areas, including privacy, neural networks, economics and contract theory, statistical inference, and quantum machine learning. Speaker: Abstract: "Traditional computing sciences have made significant advances with tools like Complexity and Worst-Case Analysis. However, Machine Learning has unveiled optimization challenges, from image generation to autonomous vehicles, that surpass the analytical capabilities of past decades. Despite their theoretical complexity, such tasks often become more manageable in practice, thanks to deceptively simple yet efficient techniques like Local Search and Gradient Descent.In this talk, we will delve into the effectiveness of these algorithms in complex environments and discuss developing a theory that transcends traditional analysis by bridging theoretical principles with practical applications. We will also explore the behavior of these heuristics in multi-agent strategic environments, evaluating their ability to achieve equilibria using advanced tools from Optimization, Statistics, Dynamical Systems, and Game Theory. The discussion will conclude with an outline of future research directions and my vision for a computational understanding of multi-agent Machine Learning. Location: CoRE 301 Committee: |
Start Date: 01 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Mitigating the Risks of Large Language Model Deployments for a Trustworthy Cyberspace Bio: Tianxing He is a postdoctoral researcher working with Prof. Yulia Tsvetkov at the University of Washington. His research is focused on natural language generation (NLG) with large language models (LLMs). He did his Ph.D. at MIT CSAIL under the guidance of Prof. James Glass, where he worked towards a better understanding of LM generation. He received his Master degree from the SpeechLab at Shanghai Jiao Tong University (SJTU) with Prof. Kai Yu, and a Bachelor degree from ACM class at SJTU. Tianxing currently works on developing algorithms or protocols for a trustworthy cyberspace in the era of large language models. He is also interested in the critical domains of monitoring, detecting, and mitigating various behaviors exhibited by language models under diverse scenarios. Tianxing’s research is recognized with accolades, including the UW Postdoc Research Award, the CCF-Tencent Rhino-Bird Young Faculty Open Research Fund, and The ORACLE Project Award. He is a recipient of the Best Paper Award at NeurIPS-ENLSP 2022. Speaker: Abstract: Large language models (LLMs) have ushered in transformative possibilities and critical challenges within our cyberspace. While offering innovative applications, they also introduce substantial AI safety concerns. In my recent research, I employ a comprehensive approach encompassing both red teaming, involving meticulous examination of LLM-based systems to uncover potential vulnerabilities, and blue teaming, entailing the development of algorithms and protocols to enhance system robustness.In this talk, I will delve into three recent projects focused on evaluation, detection, and privacy. (1) Can we trust LLMs as reliable natural language generation (NLG) evaluation metrics? We subject popular LLM-based metrics to extensive stress tests, uncovering significant blind spots. Our findings illuminate clear avenues for enhancing the robustness of these metrics. (2) How can we ensure robust detection of machine-generated text? We introduce SemStamp, a semantic watermark algorithm that performs rejection sampling in the semantic space during LLM generation. The inherent properties of semantic mapping render the watermark resilient to paraphrasing attacks. (3) How do we protect the decoding-time privacy in prompted generation with online services like ChatGPT? The current paradigm gives zero option to users who want to keep the generated text to themselves. We propose LatticeGen, a cooperative framework in which the server still handles most of the computation while the client controls the sampling operation. The key idea is that the true generate sequence is mixed with noise tokens by the client and hidden in a noised lattice. To wrap up, I will outline future directions in the realm of AI safety, addressing the evolving challenges and opportunities that lie ahead. Location: CoRE 301 Committee: |
Start Date: 04 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Towards a Unified Theory of Approximability of Globally Constrained CSPs Bio: Suprovat Ghoshal is currently a postdoc at Northwestern University and Toyota Technological Institute at Chicago, hosted by Konstantin Makarychev and Yury Makarychev. Before this, he was a postdoc at the University of Michigan, hosted by Euiwoong Lee. He received his Ph.D. from the Indian Institute of Science (IISc), where he was advised by Arnab Bhattacharyya and Siddharth Barman. His thesis received an honorable mention at the ACM India Doctoral Dissertation Award and a Best Alumni Thesis Award from IISc. He is primarily interested in exploring the landscape of optimization problems using the theory of approximation algorithms and the hardness of approximation. Speaker: Abstract: Approximation algorithms are a natural way of dealing with the intractability barrier faced by many fundamental computational problems in discrete and continuous optimization. The past couple of decades have seen vast progress in this area, culminating in unified theories of algorithms and hardness for several fundamental classes of problems, such as Maximum Constraint Satisfaction Problems (Max-CSPs). However, a similarly complete understanding of many fundamental generalizations of these classes is still yet to be realized, and in particular, the challenges in this direction represent some of the central open questions in the theory of algorithms and hardness.In this talk, I will present some recent results that build towards a theory of optimal algorithms and hardness for Globally Constrained CSPs (Constraint Satisfaction Problems), a class of problems that vastly generalize Max-CSPs. These results are derived using recently emerging tools in the theory of approximation, such as the Small-Set Expansion Hypothesis and the Sum-of-Squares Hierarchy, and they yield the first nearly tight bounds for classical fundamental problems such as Densest-k-Subgraph and Densest-k-SubHypergraph, in the regime where k is linear in the number of vertices. I will conclude by describing this research program's broad, long-term goals, as well as some specific open questions that represent key bottlenecks towards its realization. Location: CoRE 301 Committee: |
Start Date: 05 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Building Transparency in Representation Learning Bio: Yaodong Yu is a PhD student in the EECS department at UC Berkeley, advised by Michael I. Jordan and Yi Ma. His research focuses on foundations and applications of trustworthy machine learning, including interpretable deep neural networks, privacy-preserving foundation models, and uncertainty quantification under complex environments. His research has been recognized by the CPAL-2024 Rising Star Award. He is the recipient of first place in the NeurIPS-2018 Adversarial Vision Challenge. Speaker: Abstract: Machine learning models trained on vast amounts of data have achieved remarkable success across various applications. However, they also pose new challenges and risks for deployment in real-world high-stakes domains. Decisions made by deep learning models are often difficult to interpret, and the underlying mechanisms remain poorly understood. Given that deep learning models operate as black-boxes, it is challenging to understand, much less resolve, various types of failures in current machine learning systems.In this talk, I will describe our work towards building transparent machine learning systems through the lens of representation learning. First, I will present a white-box approach to understanding transformer models. I will show how to derive a family of mathematically interpretable transformer-like deep network architectures by maximizing the information gain of the learned representations. Furthermore, I will demonstrate that the proposed interpretable transformer achieves competitive empirical performance on large-scale real-world datasets, while learning more interpretable and structured representations than black-box transformers. Next, I will present our work on training the first set of vision and vision-language foundation models with rigorous differential privacy guarantees, and demonstrate the promise of high-utility differentially private representation learning. To conclude, I will discuss future directions towards transparent and safe AI systems we can understand and trust. Location: CoRE 301 Committee: |
Start Date: 07 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Mathematical Foundations for Trustworthy Machine Learning Bio: Lunjia Hu is a final-year Computer Science PhD student at Stanford University, advised by Moses Charikar and Omer Reingold. He works on advancing the theoretical foundations of trustworthy machine learning, addressing fundamental questions about interpretability, fairness, robustness, and uncertainty quantification. His works on algorithmic fairness and machine learning theory have received Best Student Paper awards at ALT 2022 and ITCS 2023. Speaker: Abstract: Machine learning holds significant potential for positive societal impact. However, in critical applications involving people such as healthcare, employment, and lending, machine learning raises serious concerns of fairness, robustness, and interpretability. Addressing these concerns is crucial for making machine learning more trustworthy. This talk will focus on three lines of my recent research establishing the mathematical foundations of trustworthy machine learning. First, I will introduce a theory that optimally characterizes the amount of data needed for achieving multicalibration, a recent fairness notion with many impactful applications. This result is an instance of a broader theory developed in my research giving the first sample complexity characterizations for learning tasks with multiple interacting function classes (ALT’22 Best Student Paper, ITCS’23 Best Student Paper). Next, I will discuss my research in omniprediction, a new approach to robust learning that allows for simultaneous optimization of different loss functions and fairness constraints (ITCS'23, ICML’23). Finally, I will present a principled theory of calibration of neural networks (STOC’23). This theory provides an essential tool for understanding uncertainty quantification and interpretability in deep learning, allowing rigorous explanations for interesting empirical phenomena (NeurIPS'23 spotlight, ITCS'24). Location: CoRE 301 Committee: |
Start Date: 08 Mar 2024; Start Time: 10:00AM - 11:00AM Title: Simplification of Boolean Expressions using Karnaugh Map Bio: Murtadha Aldeer graduated with a Ph.D. in Electrical and Computer Engineering from WINLAB/Rutgers University in October 2023 where he was supervised by Professor Richard Martin and Professor Jorge Ortiz. He is currently an Assistant Teaching Professor at Montclair State University. His research interests include Cyber-Physical Systems, Connected Health, Internet of Things, and Smart Buildings. He is passionate about teaching, mentoring students and community organizing. He has taught a variety of courses in computer science and computer engineering since 2018. Speaker: Abstract: This lecture will explore the fundamentals of Boolean Algebra with a particular emphasis on simplifying Boolean expressions using Karnaugh-Maps (K-maps). We will demonstrate how this method efficiently simplifies Boolean expressions, which is invaluable for minimizing Logic Circuits. Location: CoRE 301 Committee: |
Start Date: 13 Mar 2024; Start Time: 09:00AM - 11:00AM Title: Causal Collaborative Filtering Bio: Speaker: Abstract: In the era of information explosion, recommender systems have become essential for fulfilling users' personalized and complex demands across various services like e-commerce and social media. Collaborative filtering algorithms, fundamental to these systems, traditionally leverage similarities between users and items to provide recommendations, focusing on mining correlative patterns. However, this dissertation introduces causal collaborative filtering methods based on the structural causal model framework to address issues like Simpson's paradox, confounding bias, and echo chambers. These methods shift from correlative to causal learning by formulating recommendations as "what if" questions and applying causal inference techniques. The dissertation presents a comprehensive approach that mitigates various challenges through different types of causal graphs and inference techniques, providing a significant advancement in the field of recommender systems. Location: CoRE 305 Committee: Prof. Yongfeng Zhang (advisor) Prof. Hao Wang Prof. Desheng Zhang Prof. Hamed Zamani (external) |
Start Date: 13 Mar 2024; Start Time: 04:00PM - 05:30PM Title: Fairness in Recommender Systems Bio: Speaker: Abstract: As one of the most pervasive applications of machine learning, recommender systems are playing an important role on assisting human decision making, which gives rise to essential concerns regarding the fairness of such systems. Research on fair machine learning has mainly focused on classification and ranking tasks. Although recommendation algorithm can usually be considered as a type of ranking algorithm, the fairness concerns in recommender systems are more complicated and should be extended to multiple stakeholders. In specific, different from only concerning item exposure fairness in ranking problem, we should also attach importance to the fairness demands of users in recommender systems. To improve user-side fairness in recommendation, we have proposed three works which concentrate on user group-level fairness, user individual-level fairness, and enhancing fairness for cold-start users, respectively. Location: CoRE 301 Committee: Prof. Yongfeng Zhang (Advisor) Prof. Hao Wang Prof. Amélie Marian Prof. Yi Zhang (external) |
Start Date: 15 Mar 2024; Start Time: 08:45PM - 10:00PM Title: Large Language Models for Data Driven Applications Bio: Speaker: Abstract: This dissertation presents a series of innovative approaches leveraging deep learning and Large Language Models to address challenges in various steps in the pipeline of real-world data driven applications.Firstly, we explore the enhancement of locality-sensitive hashing (LSH) for entity blocking through a neuralization approach. Entity blocking is an important data pre-processing step that finds similar data records that might refer to the same real-world entity. We train deep neural networks to act as hashing functions for complex metrics, which surpasses the limitations of generic similarity metrics in traditional LSH-based methods. Our novel methodology, embodied in NLSHBlock (Neural-LSH Block), leverages pre-trained language models fine-tuned with a novel LSH-based loss function. NLSHBlock achieves significant performance improvements in entity blocking tasks and can boost the performance of later steps in the data processing pipeline.Further, we introduce Sudowoodo, a multi-purpose data integration framework based on contrastive representation learning and large language models, which offers a unified solution for data integration tasks like Entity Matching. Entity matching is a process that determines if a pair of data records represent the same real-world entity and plays an essential role in plenty of applications. To tackle the common issue of insufficient number of high-quality labeled data, Sudowoodo utilizes similarity-aware data representations learned without labels and enables effective fine-tuning in the semi-supervised learning setting where only a small amount of labeled data is available. Besides, Sudowoodo also applies to other data integration tasks such as data cleaning and semantic type detection.Finally, we propose a Generate-and-Retrieve with Reasoning (GTR) framework for recommender systems, inspired by generative large language models. Entity recommendation is usually the last step in a data driven application pipeline. Our proposed framework views recommendation tasks as a process of instruction following by generative large language models, employing natural language instructions to express and decipher user preferences and intentions. GTR innovates by directly generating item names, employing state-of-the-art retrieval models for item alignment, and enhancing model performance through reasoning distillation.Through rigorous experimentation on diverse real-world datasets, we validate the effectiveness of these approaches, setting new benchmarks in their respective domains. The findings of this dissertation not only advance the state of the art in crucial steps of industrial application pipelines including entity blocking, entity matching, and entity recommendation systems, but also open promising avenues for the application of deep learning and large language models in complex data integration and recommendation tasks, fostering improved accuracy, efficiency, and user interaction. Location: FULLY REMOTE Committee: Prof. Yongfeng Zhang (advisor) Prof. Dong Deng (co-advisor) Prof. Hao Wang Dr. Xiao Qin (external member) |
Start Date: 18 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Quantum and Quantum-Inspired Computation for Next-Generation Wireless Networks Bio: Minsung Kim is a postdoctoral associate in the Department of Computer Science at Yale University. He received his Ph.D. in Computer Science from Princeton University and his B.E. in Electrical Engineering (Great Honor) from Korea University. His research focuses on quantum and emerging computing systems for next-generation wireless networks. His work has been published in the premier venues of mobile computing and wireless networking such as ACM SIGCOMM and MobiCom. He is a recipient of the 2021 Qualcomm Innovation Fellowship, the 2022 Princeton SEAS Award for Excellence, and the 2023 Adiabatic Quantum Computing (AQC) Junior Scientist Award. He was named a Siebel Scholar (Class of 2024). Speaker: Abstract: A central design challenge for future generations of wireless networks is to meet the ever-increasing demand for capacity, throughput, and connectivity. While significant progress has been made in designing advanced wireless technologies, the current computational capacity at base stations to support them has been consistently identified as the bottleneck, due to limitations in processing time. Quantum computing is a potential tool to address this computational challenge. It exploits unique information processing capabilities based on quantum mechanics to perform fast calculations that are intractable by traditional digital methods. In this talk, I will present design directions of quantum compute-enabled base station systems in wireless networks and introduce our prototype systems that are implemented on real-world quantum processors. The prototypes are designed for quantum-accelerated near-optimal wireless signal processing in Multiple-Input Multiple-Output (MIMO) systems that could drastically increase wireless performance for tomorrow's next-generation wireless cellular networking standards, as well as in next-generation wireless local area networks. I will provide design guidance of quantum, quantum-inspired classical, and hybrid classical-quantum optimization in the systems with underlying principles and technical details and discuss future research directions based on the current challenges and opportunities. Location: CoRE 301 Committee: |
Start Date: 19 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Towards Optimal Sampling Algorithms Bio: Thuy-Duong “June” Vuong is a 5th year PhD student at Stanford. Her research is in designing and analyzing algorithms for sampling from complex high-dimensional distributions, with a focus on Markov chains analysis. Her work gives the optimal bounds on the runtime of Markov chains using entropy analysis and the theory of high-dimensional expanders. She received Bachelor of Science degrees in Mathematics and Computer Science at the Massachusetts Institute of Technology. Her research is supported by a Microsoft Research PhD fellowship. Speaker: Abstract: Sampling is a fundamental task with applications in various areas including physics, statistics, and combinatorics. Many applications involve the challenging task of sampling from complex high-dimensional distributions. Markov chains are a widely adopted approach for tackling these critical problems, but current runtime analyses are suboptimal.In this talk, I will introduce “entropic independence”, a novel and powerful framework for analyzing Markov chains, and use it to obtain the tightest possible runtime bounds. My work gives the first near-linear time sampling algorithms for classical statistical physics models in the tractable regime, resolving a 70-year-old research program. My research results in highly practical algorithms and settles several long-standing open problems in sampling and approximate computing. Location: CoRE 301 Committee: |
Start Date: 19 Mar 2024; Start Time: 02:00PM - 04:00PM Title: Techniques for Increasing the Efficiency of Physics Simulation Bio: Speaker: Abstract: This work focuses on methods for improving the efficiency of simulations of 3D tetrahedral meshes representing elastic solids. These kinds of simulations are used in computer graphics for stretch/squash animations, as well as in engineering to simulate the elastic deformation of materials. Our general-purpose method speeds up such simulations, so that for any given level of processing capacity, one can simulate larger and more complicated models in a shorter period of time.Our approach focuses on reformulating mesh data for greater cache efficiency. It is much faster to access data from a cache than from memory, so whenever a datum is needed, it is better to have it in the cache than to access it from memory. When a mesh datum is called by the physics engine, its neighbors in the data are loaded into the cache as well. Since certain vertices and mesh elements are called together in the simulation code, we reorder the mesh data so that they are listed together in memory. If mesh data that are called together are listed together, they will be loaded together into the cache, and there will be a smaller chance of cache misses and page faults in the process of executing the algorithms. We identified remarkable speedups using this setup for two separate elastic solid physics simulation engines. Location: CBIM #22 Committee: Assistant Professor Mridul Aanjaneya Professor Santosh Nagarakatte Associate Professor Abdeslam Boularias Assistant Professor Roie Levin |
Start Date: 21 Mar 2024; Start Time: 10:00AM - 12:00AM Title: All-Norm Load Balancing in Massive Graphs Bio: Speaker: Abstract: We address the all-norm load balancing problem in bipartite graphs in the distributed and semi-streaming models. In the all-norm load balancing problem, we are given a bipartite graph with weights on the clients. The goal is to assign each client to an adjacent server such that the Lp norm of the server load vector is approximately minimized for all p simultaneously. We present the first O(1)-approximation algorithm in the CONGEST model that runs in polylog(n) rounds. In the semi-streaming model, we develop an O(1)-approximation O(log n)-pass algorithm using different techniques. Additionally, these algorithms are can be ported to the sequential model, yielding the first O(1)-approximation for the problem that runs in near-linear time. Location: CoRE 305 Committee: Aaron Bernstein (advisor) Sepehr Assadi Jie Gao Christian Konrad (external) |
Start Date: 21 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Reliable Machine Learning by Integrating Context Bio: Chengzhi Mao is a postdoctoral research fellow and prior Ph.D. student from the Department of Computer Science at Columbia University, advised by Prof. Carl Vondrick and Junfeng Yang. He is also a core faculty member at MILA, Quebec AI Institute, since 2023. He received his Bachelor's from Tsinghua University. His research resides in trustworthy machine learning and computer vision. His work has led to over 20 publications and Orals at top computer vision and machine learning conferences, which have been covered by Science and MITNews. He is a recipient of the CVPR doctoral award in 2023. Speaker: Abstract: Machine learning is now widely used and deeply embedded in our lives. However, despite the excellent performance of machine learning models on benchmarks, state-of-the-art methods like neural networks often fail once they encounter realistic settings. Since neural networks often learn correlations without reasoning with the right signals and knowledge, they fail when facing shifting distributions, unforeseen corruptions, and worst-case scenarios. Since neural networks are black boxes, they are not interpretable and not trusted by the user. In this talk, I will show how to build reliable machine learning by tightly integrating context into the models. The context has two aspects: the intrinsic structure of natural data, and the extrinsic structure of domain knowledge. Both are crucial: By capitalizing on the intrinsic structure in natural images, I show that we can create adaptive computer vision systems that are robust, even in the worst case, an analytical result that also enjoys strong empirical gains. Through the integration of external knowledge, such as causal structure, my framework can instruct models to use the right signals for visual recognition, enabling new opportunities for controllable and interpretable models. I will also talk about future work on reliable foundation models. Location: CoRE 301 Committee: |
Start Date: 22 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Learning from Interaction Bio: Kianté Brantley is a Postdoctoral Associate in the Department of Computer Science at Cornell University., working with Thorsten Joachims. He completed his Ph.D. in Computer Science at the University of Maryland College Park, advised by Dr. Hal Daumé III. His research focuses on developing machine learning models that can make automated decisions in the real world with minimal supervision. His research lies at the intersection of imitation learning, reinforcement learning, and natural language processing. He is a recipient of the NSF LSAMP BD Fellowship, ACM SIGHPC Computational and Data Science Fellowship, Microsoft Dissertation Research Grant, Ann G. Wylie Dissertation Fellowship, and NSF CIFellow Postdoctoral Fellowship. Speaker: Abstract: Machine learning systems have seen advancements due to large models pre-trained on vast amounts of data. These pre-trained models have led to progress on various downstream tasks when fine-tuned. However, for machine learning systems to function in real-world environments, they must overcome certain challenges that are not influenced by model or dataset sizes. One potential solution is to fine-tune machine learning models based on online interactions. In this talk, I will present my research on developing natural language processing systems that learn from interacting in an environment. I will begin by describing the issues that arise when systems are trained on offline data and then deployed in interactive environments. Additionally, I will present an algorithm that addresses these issues using only environmental interaction without additional supervision. Moreover, I will demonstrate how learning from interaction can improve natural language processing systems. Finally, I will present a set of new interactive learning algorithms explicitly designed for natural language processing systems. Location: CoRE 301 Committee: |
Start Date: 25 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Types and Metaprogramming for Correct, Safe, and Performant Software Systems Bio: Guannan Wei is currently a postdoctoral researcher at Purdue University. His research interests lie in programming languages and software engineering. His contributions have been published in flagship programming languages and software engineering venues, such as POPL, OOPSLA, ICFP, ECOOP, ICSE, and ESEC/FSE. Guannan received his PhD degree (2023) in Computer Science from Purdue University, advised by Tiark Rompf. He is the 2022 recipient of the Maurice H. Halstead Memorial Award for Software Engineering Research. More of Guannan’s work can be found at https://continuation.passing.style. Speaker: Abstract: In this talk, I will present some novel directions to build correct, safe, and performant software systems using programming languages and metaprogramming techniques. In the first part of the talk, I will present reachability type systems, a family of static type systems to track sharing, separation, and side effects in higher-order imperative programs. Reachability types lead to a smooth combination of Rust-style ownership types with higher-level programming abstractions (such as first-class functions). In the second part, I will discuss how metaprogramming techniques can help build correct, flexible, and performant program analyzers. I will present GenSym, a parallel symbolic-execution compiler that is derived from a high-level definitional symbolic interpreter using program generation techniques. GenSym generates code in continuation-passing style to perform parallel symbolic execution of LLVM IR programs, and significantly outperforms similar state-of-the-art tools. The talk also covers my future research agenda, including applications of reachability types in quantum computing. Location: CoRE 301 Committee: |
Start Date: 26 Mar 2024; Start Time: 10:30AM - 12:00PM Title: Building Networked Systems & Protocols for Terabit Ethernet Bio: Qizhe Cai is a Ph.D. student in the Computer Science Department at Cornell University, advised by Prof. Rachit Agarwal. His research lies at the intersection of networking and operating systems, with a focus on building efficient network systems and protocols to exploit the benefits of Terabit Ethernet. He was awarded the Meta Fellowship in 2022. Speaker: Abstract: Datacenter servers will soon have Terabit Ethernet. However, design of host network stacks that are able to fully exploit the benefits of Terabit Ethernet hardware remains elusive.In this talk, I will first present insights from an in-depth study on understanding fundamental limitations of existing network stacks in terms of exploiting the benefits of Terabit hardware. I will then present NetChannel, a new host network stack architecture that enables elastic allocation and scheduling of host resources across applications, enabling many previously unachievable operating points (e.g., single-threaded applications to saturate multi-hundred gigabit links). I will also discuss how my recent work has led to a myriad of new questions on redesigning network protocols, stacks, and hardware for Terabit Ethernet. Location: CoRE 301 Committee: |
Start Date: 27 Mar 2024; Start Time: 03:00PM - 05:00PM Title: Automated Machine Learning for Intelligent Systems Bio: Speaker: Abstract: The fast progress in Machine Learning techniques has led to a growing impact of Artificial Intelligence (AI) on various aspects of people's lives. AI model learning comprises three vital components: data inputs, model design, and loss functions. Each of these components makes a significant contribution to the AI system's performance. Traditionally, these components needed skilled domain experts to meticulously design them, creating a challenging barrier to entry into AI. Besides, manual approaches are relatively inefficient and often fail to achieve optimal results. Recently, automated machine learning (AutoML), such as neural architecture search, has tried to tackle the challenge by automating the design and parameters of deep models. However, traditional AutoML research mainly focuses on automated model design instead of the inputs and loss functions, and AutoML's research on recent large language models is still in its infancy due to the enormous computations required. Through the development of automated machine learning techniques at various stages of an AI pipeline, we conduct three studies to advance both small-scale and large-scale intelligent systems further, making them more precise, effective, and user-friendly. Location: CoRE 305 Committee: Professor Yongfeng Zhang (Chair) Assistant Professor Hao Wang Assistant Professor He Zhu Professor Mengnan Du (external) |
Start Date: 29 Mar 2024; Start Time: 10:30AM - 12:00PM Title: When and why do simpler-yet-accurate models exist? Bio: Lesia Semenova is a final-year Ph.D. candidate at Duke University in the Department of Computer Science, advised by Cynthia Rudin and Ronald Parr. Her research interests span responsible and trustworthy AI, interpretable machine learning, reinforcement learning, and AI in healthcare. She has developed a foundation for the existence of simpler-yet-accurate machine learning models. She was selected as one of the 2024 Rising Stars in Computational and Data Sciences. The student teams she has coached won the ASA Data Challenge Expo twice and placed third in a competition on scholarly document processing. Prior to joining Duke, she worked for two years at the Samsung Research and Development Institute Ukraine. Speaker: Abstract: Finding optimal, sparse, accurate models of various forms (such as linear models with integer coefficients, rule lists, and decision trees) is generally NP-hard. Often, we do not know whether the search for a simpler model will be worthwhile, and thus we do not undertake the effort to find one. This talk addresses an important practical question: for which types of datasets would we expect interpretable models to perform as well as black-box models? I will present a mechanism of the data generation process, coupled with choices usually made by the analyst during the learning process, that leads to the existence of simpler-yet-accurate models. This mechanism indicates that such models exist in practice more often than one might expect. Location: CoRE 301 Committee: |
Start Date: 29 Mar 2024; Start Time: 02:00PM - 04:00PM Title: Exploiting pre-trained large-scale text-to-image diffusion models for image & video editing Bio: Speaker: Abstract: Recent advancements in diffusion models have significantly impacted both image and video domains, showcasing remarkable capabilities in text-guided synthesis and editing. In the realm of image editing, particularly for single images like iconic paintings, existing approaches often face challenges such as overfitting and content preservation. To overcome these, a novel approach has been developed that introduces a model-based guidance technique, enhancing the pre-trained diffusion models with the ability to maintain original content while incorporating new features as directed by textual descriptions. This method includes a patch-based fine-tuning process, enabling the generation of high-resolution images and demonstrating impressive editing capabilities, including style modification, content addition, and object manipulation. Extending the prowess of diffusion models to the video sector, text-guided video inpainting presents its own set of challenges, including maintaining temporal consistency, handling various inpainting types with different structural fidelity, and accommodating variable video lengths. The introduction of the Any-Length Video Inpainting with Diffusion Model (AVID) addresses these issues head-on. AVID incorporates effective motion modules and adjustable structure guidance for fixed-length video inpainting and introduces a Temporal MultiDiffusion sampling pipeline with a middle-frame attention guidance mechanism. This innovative approach enables the creation of videos of any desired length, ensuring high-quality inpainting across a wide range of durations and types. Through extensive experimentation, both methodologies have proven their effectiveness, pushing the boundaries of what's possible in image and video editing with diffusion models. Publication:1. Zhang, Zhixing, Ligong Han, Arnab Ghosh, Dimitris N. Metaxas, and Jian Ren. "Sine: Single image editing with text-to-image diffusion models." In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6027-6037. 2023.2. Zhang, Zhixing, Bichen Wu, Xiaoyan Wang, Yaqiao Luo, Luxin Zhang, Yinan Zhao, Peter Vajda, Dimitris Metaxas, and Licheng Yu. "AVID: Any-Length Video Inpainting with Diffusion Model." arXiv preprint arXiv:2312.03816 (2023). Location: CoRE 305 Committee: Professor Dimitris Metaxas Assistant Professor Yongfeng Zhang Associate Professor Konstantinos Michmizos Professor Mario Szegedy |
Start Date: 01 Apr 2024; Start Time: 10:30AM - 12:00PM Title: Programmable Software Systems for Correct High-performance Applications Bio: Konstantinos Kallas is a PhD student at the University of Pennsylvania working with Rajeev Alur. He is interested in building systems that enable the development of high-performance applications with robust correctness guarantees, both in theory and in practice. His research has appeared at several venues including OSDI, NSDI, EuroSys, POPL, OOPSLA, and VLDB, and has received the best paper award at EuroSys 21, the best presentation award at HotOS 21, and the 2nd place at the ACM SRC Grand Finals. His research on optimizing shell scripts for parallel and distributed computing environments is supported by the Linux Foundation and part of his research on serverless is incorporated in the Durable Functions framework that is offered by Azure and serves thousands of active users. You can find more information about him on his website: https://www.cis.upenn.edu/~kallas/. Speaker: Abstract: We live in an era of unprecedented compute availability. The advent of the cloud allows anyone to deploy critical high-performance applications that serve millions of users without owning or managing any computational resources. The goal of my research is to enable the development of such high-performance applications with robust correctness guarantees. To achieve this goal, I build practical programmable software systems that target realistic workloads in widely-used environments. My systems are rooted in solid foundations, incorporating formal specifications and techniques drawn from the programming languages, compilers, and formal methods literature.In this talk I will present some of my work on such systems, including PaSh, the first optimization system for the Unix shell since its inception 50 years ago, as well as MuCache, a caching system for microservice graphs. Surprisingly, the shell and microservices have a key characteristic in common, they are both used to compose black-box components to create applications that are greater than the sum of their parts. I will conclude the talk by arguing that systems research is a key requirement to support the increased compute demands of new applications and enable future breakthroughs. Location: CoRE 301 Committee: |
Start Date: 02 Apr 2024; Start Time: 10:30AM - Title: Backdoor in AI: Algorithms, Attacks, and Defenses Bio: Speaker: Abstract: Location: CoRE 301 Committee: |
Start Date: 16 Apr 2024; Start Time: 03:30PM - Title: Tractability Frontiers in Coordinated Motion Planning Bio: Speaker: Abstract: Location: Committee: |
Start Date: 23 Apr 2024; Start Time: 11:00AM - 01:00PM Title: Fair and Accurate Machine Learning in Dynamic and Multi-domain Settings Bio: Speaker: Abstract: Location: Committee: |
Start Date: 01 May 2024; Start Time: 03:00PM - Title: Maximize Utilization of Support-Set for Few-shot segmentation Bio: Speaker: Abstract: Location: Committee: |
Start Date: 10 May 2024; Start Time: 11:00AM - 12:30PM Title: Exploring Structured Noise for Private Data Release Bio: Speaker: Abstract: Differential privacy has become the de-facto standard for ensuring privacy in applications that deal with sensitive data. Oftentimes, practical deployments of differentially private algorithms demand additional control on the private output of algorithms. I will talk about our work that focuses on providing algorithms when additional such properties are required from the private algorithms without relying on post-processing. The first problem considers releasing private histograms with invariant constraints for integer valued data. We introduce a new privacy notion, called integer subspace differential privacy, and propose mechanisms with integer valued noise that respect specified constraints on the histogram for both pure and approximate differential privacy. The second problem considers answering differentially private range queries with consistency and transparency imposed on the query output. Consistency intuitively means that multiple query answers do not immediately introduce contradiction with each other and transparency asks for the distribution of introduced noises to be available in closed forms. Our mechanism consists of a carefully constructed covariance matrix for answering queries with input perturbation. We give an algorithm that samples from this noise distribution in linear time and show that we obtain optimal $\ell_2$ error and near optimal $\ell_\infty$ error. Both problems are motivated from application of differential privacy to the release of 2020 U.S. Decennial Census. Location: CoRE 305 Committee: Professor Jie Gao Assistant Professor Sumegha Garg Assistant Professor Peng Zhang Assistant Professor Mridul Aanjaneya |
Start Date: 14 May 2024; Start Time: 08:00AM - 05:00PM Title: AI/GenAI CARTA SYMPOSIUM Bio: Speaker: Abstract: Location: 100 Rockafeller Road, Piscataway, NJ Committee: |
Start Date: 21 May 2024; Start Time: 02:00PM - 03:00PM Title: Formal Verification of the eBPF Verifier: Opportunities, Challenges, and Initial Approaches Bio: Speaker: Abstract: eBPF is an innovative technology that allows developers to extend the Linux kernel's functionality by loading custom written programs dynamically. Programs written in eBPF are used extensively in industry for network observability, performance profiling, and security tools. Due to the safety critical nature of the Linux kernel, loaded eBPF programs must not pose security risks. To ensure eBPF programs are safe when loaded into the kernel, a static analyzer, called the eBPF verifier, checks all possible values the program variables may take in all possible executions of the program. However, the static analysis done by the verifier is unsound and, as a result, many critical bugs have been discovered. In this talk I will present our work on formally verifying the eBPF verifier's range tracking analysis by 1) formally specifying soundness conditions of the analysis and 2) generating encodings of the verifier's operators in first order logic and comparing against our soundness specification. We also propose a program synthesis framework to generate eBPF programs that expose bugs in the verifier when our analysis deems the verifier's operators unsound.The list of papers exam will be based on: https://docs.google.com/spreadsheets/d/1vtqoC4_BiTiu26Vuf3gqMa2Sweg4PqaKrFPP_ADkIE/edit#gid=1386834576 Location: CoRE 305 Committee: Professor Santosh Nagarakatte Assistant Professor Srinivas Narayana Assistant Professor He Zhu Distinguished Professor Dimitris Metaxas |
Start Date: 25 Jun 2024; Start Time: 04:00PM - 05:30PM Title: Certifiable Controller Synthesis for Underactuated Robotic Systems: From Convex Optimization to Learning-based Control Bio: : Lujie Yang (https://lujieyang.github.io/) is a 4th year PhD student at MIT EECS, advised by Prof. Russ Tedrake. Her research seeks to enable robots to operate robustly and intelligently, with theoretical guarantees, by combining optimization, control theory and machine learning. Lujie was the recipient of the Presidential Graduate Fellowship, Richard C. Dupont Fellowship and Tung/Lewis Fellowship at MIT. She won the best presentation award at MIT LIDS student conference 2023 and got honorable mention for 2023 T-RO King-Sun Fu Memorial best paper award of the year. Speaker: Abstract: Many interesting robotic tasks, such as running, flying, and manipulation, require certifiable controllers to operate robustly and intelligently. In this presentation, I will talk about how to synthesize controllers with optimality and stability guarantees using both convex optimization and learning-based methods.1. Approximate optimal controller synthesis with SOS: I will discuss the potential of sums-of-squares (SOS) optimization in synthesizing certifiable controllers for nonlinear dynamical systems. We demonstrate that SOS optimization can generate dynamic controllers with bounded suboptimal performance for various underactuated robotic systems by finding good approximations of the value function.2. Certifiable Lyapunov-stable neural controller synthesis with learning: I will address the advancements in neural-network-based controllers driven by deep learning. Despite their progress, many of these controllers lack critical stability guarantees, essential for safety-critical applications. We introduce a novel framework for learning neural-network controllers along with Lyapunov stability certificates, bypassing the need for costly SOS, MIP, or SMT solvers. Our framework’s flexibility and efficiency enable the synthesis of Lyapunov-stable output feedback control using NN-based controllers and observers with formal stability guarantees for the first time in literature.3. Contact-rich manipulation: I will also provide a brief overview of our recent work on global planning for contact-rich manipulation. By interpreting the empirical success of reinforcement learning from a model-based perspective, we have developed efficient model-based motion planning algorithms that achieve results comparable to reinforcement learning, but with dramatically less computation. Location: Online talk and SPR-403 Committee: |
Start Date: 01 Jul 2024; Start Time: 11:00AM - 01:00PM Title: Deep Generative Models: Controllability, Efficiency, and Beyond Bio: Speaker: Abstract: The rapid evolution of deep generative models has unlocked unprecedented capabilities in AI, pushing the boundaries of creativity, personalization, and efficiency. This dissertation explores two works that exemplify the integration of controllability and efficiency in the domain of generative AI, specifically focusing on text-to-image diffusion models. First, I discuss our parameter-efficient approach for personalizing text-to-image diffusion models. By optimizing the singular values of weight matrices, this method facilitates the adaptation of pre-trained models to new tasks and capabilities with minimal data, enabling concept composition and image editing. The second work focuses on leveraging diffusion inversion techniques for controlled image editing and solving inverse problems. By developing approximate algorithms for optimization-based methods, we achieve not only time efficiency but also enhanced performance. Location: CoRE 301 Committee: Prof. Dimitris Metaxas (Chair) Prof. Vladimir Pavlovic Prof. Hao Wang Prof. Qiang Liu (external) |
Start Date: 19 Jul 2024; Start Time: 10:00AM - 11:30AM Title: Reconstructing 3D Humans and Animals from Visual Data Bio: Speaker: Abstract: This dissertation explores the problem of reconstructing humans and animals from visual data. Given the large number of applications that require a 3D model as input like augmented and virtual reality (AR/VR), film production, and forensics, the ability to obtain accurate 3D models from images is more relevant than ever. Recent advancements in 3D human mesh recovery have significantly enhanced our ability to reconstruct humans in 3D with remarkable precision. Despite these successes, current 3D perception systems still lag behind their 2D counterparts in terms of robustness. In this talk, I will first outline our latest efforts to enhance the accuracy of 3D human recovery, with the help of automatically detected image observations (e.g., 2D keypoint detections), and address the limitations of existing work for this task. Then, I will present our work on 3D animal reconstruction. I will discuss the challenges associated with this task, particularly the absence of ground truth 3D data and the scarcity of 2D annotations, and propose weaker forms of supervision that are effective in overcoming this limitation. Location: CoRE 301 Committee: Prof. Dimitris Metaxas (chair) Prof. Karl Stratos Prof. Konstantinos Michmizos Prof. Sharon Xiaolei Huang (external) |
Start Date: 29 Jul 2024; Start Time: 11:00AM - 12:30PM Title: Toward a Trustworthy Digital Future: Robust Online Machine Learning and Intelligent Fact-Checking Bio: Yupeng Li received his PhD degree in computer science at The University of Hong Kong. He was a postdoctoral research fellow at the University of Toronto. He is an assistant professor with the Department of Interactive Media at Hong Kong Baptist University (HKBU). He is also a Director of a Master program and had been Associate Director (Research and Technology) of HKBU Fact Check Center. He is interested in studying trustworthy machine learning in networking and social computing. He is excited about interdisciplinary research that applies robust algorithmic techniques to edging problems. Dr. Li takes advantage of powerful techniques of learning, algorithm, and game theory to design and analyze networked systems, such as information and social networks. His works have been accepted in venues such as MobiHoc, The ACM Web Conference, INFOCOM, ICDCS, JSAC, ToN, TMC, and ICA. Dr. Li has been awarded the distinction of Distinguished TPC Member of the IEEE INFOCOM 2022 and 2024 and the Rising Star in Social Computing Award by CAAI. He serves on several technical committees of top conferences in computing-related areas. He was the TPC Co-Chairs for an ICDCS Research Track in 2024 and SocialMeta 2023. Speaker: Abstract: Online machine learning is a computing paradigm where agents cooperate to predict online data samples in a centralized or decentralized AI system. Despite its competitive capability in handling large-scale online data, it is yet to be widely adopted in real-world applications due to the challenges in robustness in the presence of the endogenous and exogenous threats. This talk will address the trustworthiness of such AI systems and introduce our recent efforts in threat-resilient (de)centralized online learning mechanisms. The trustworthiness concerns lie in the information that the AI systems interact with as well. Our world is increasingly suffering from unrestrained spread of misinformation in many areas. Intelligent fact-checking becomes more important in the era of Generative AI. This talk will also introduce our research in combating misinformation. We will address the robustness of rumor detection techniques as well as a carefully constructed benchmarking dataset for fake news detection. The dissemination of misinformation has propelled fact-checking to the forefront of academic research and societal concerns. Aiming at building a trustworthy digital future, we believe our research can help make our world a better one. Location: Hill 482 Committee: |
Start Date: 23 Aug 2024; Start Time: 10:00PM - 11:30PM Title: Integrate Learning and Reasoning for Large Language Model and Recommender Systems Bio: Speaker: Abstract: In the current era, recommendation systems has become increasingly integral to our daily lives. Despite the significant advancements in recommendation systems, many models still lack robust reasoning capabilities, which limits their effectiveness and reliability. This research aims to address this gap by enhancing the reasoning abilities of recommendation systems to improve their overall performance.Our initial focus was on integrating counterfactual reasoning and logical reasoning abilities into recommendation models. By applying these reasoning techniques, we observed a marked improvement in the performance of recommendation systems, demonstrating the potential of reasoning-enhanced models in practical applications. Building on these findings, we extended our approach to large language models (LLMs). Our experiments showed that incorporating logical reasoning into LLMs significantly enhanced their performance across various benchmarks. Given their extensive use in natural language processing tasks, we aimed to improve their text reasoning abilities to enhance recommendation performance. This ensures that these models can understand, process, and respond logically to complex textual information.However, the rapid development of large language models also brings forth ethical challenges. It is imperative that we do not solely focus on optimizing model performance without addressing potential moral and ethical concerns. Recognizing this, we developed a benchmark to evaluate the moral reasoning ability of LLMs. This benchmark assesses the ethical implications of the models' outputs, ensuring that they align with societal values and norms. Location: Virtual Committee: Prof. Yongfeng Zhang (Advisor) Prof. Dong Deng Prof. Hao Wang Dr. Yan Liang (external, Senior Applied Scientist) |
Start Date: 29 Aug 2024; Start Time: 01:00PM - 03:00PM Title: Accelerating software packet processing for high-speed networks Bio: Speaker: Abstract: The rapid growth of emerging applications, such as virtual reality (VR), deep neural network (DNN) model training and inference, and high-resolution video streaming, has significantly increased the demand for high-throughput and low-latency networks, which are often bottlenecked by packet processing. Software packet processing, such as the kernel network stack, is widely deployed and thus worth accelerating. This thesis focuses on software packet processing with the goal of bridging the performance between the current packet processing mechanisms and the full potential of the underlying hardware. Two systems are presented: K2, a compiler that optimizes BPF bytecode (i.e., a packet-processing program that can be attached in the kernel network stack) to enhance packet processing performance while ensuring formal correctness and safety (unsafe programs will be rejected by the BPF verifier and cannot be installed into the kernel), and SCR (state-compute replication), a principle for scaling throughput of stateful packet processing across multiple cores using replication. Experimental results demonstrate that K2 produces code with 6–26% reduced size, 1.36%–55.03% lower average packet-processing latency, and 0–4.75% higher throughput (packets per second per core) relative to the best clang-compiled program, across benchmarks drawn from Cilium, Facebook, and the Linux kernel. SCR enables linear scaling of packet-processing throughput with the number of cores, independent of flow size distributions. Location: CoRE 305 Committee: Prof. Srinivas Narayana (advisor/chair) Prof. Richard Martin Prof. He Zhu Prof. Mina Tahmasbi Arashloo (external) |
Start Date: 09 Sep 2024; Start Time: 10:30AM - 12:00PM Title: Programming Computer Networks Safely and Efficiently Bio: Srinivas Narayana is an Assistant Professor in the Department of Computer Science at Rutgers University. Srinivas's research goal is to enable developers to implement expressive networked applications with guarantees of safety and efficiency, by advancing domain-specific compiler and formal methods technology that improves Internet software and hardware. Srinivas received his M.A. and Ph.D. in Computer Science from Princeton University in 2016 and completed a post-doc at Massachusetts Institute of Technology in 2018. Srinivas's research has been recognized with distinguished paper awards at the Code Generation and Optimization (CGO) 2022 conference and the ACM SIGCOMM 2017 conference, and grants from the National Science Foundation, Meta, the Network Programming Institute, and the eBPF foundation. Speaker: Abstract: Over the last two decades, computing has been driven by a demand to process large datasets and build Internet services that support millions of users. While the demands on computing have exploded, the capabilities of general-purpose compute hardware have stagnated, due to the demise of Moore's law. Commodity network software stacks lag far behind the speed and flexibility desired in moving data between applications and processing data in transit.The prevailing approach to address network stack inefficiency is *software specialization*: moving away from the fully-featured network stacks in commodity operating system kernels, and avoiding most software code paths typically executed during data movement through the network stack. Specialization makes it possible to build high-speed applications, but it does not make it easy: Application developers are forced to also become experts in developing low-level system software.My research addresses three fundamental challenges standing in the way of effective software specialization for networking: safety, efficiency, and flexibility, by (i) developing principles andalgorithmic approaches to improve the efficiency of high-speed network software, with guarantees of safety and correctness; (ii) designing sound static analyzers to prove the safety of expressive low-level network software; and (iii) developing efficient compilation techniques to run expressive networking on high-speed network hardware. Location: CoRE 301 Committee: |
Start Date: 10 Sep 2024; Start Time: 10:30AM - 12:00PM Title: Pursuing Transparency and Accountability in Data and Decision Processes Bio: Amélie Marian is an Associate Professor in the Computer Science Department at Rutgers University. Her research interests are in Explainable Rankings, Accountability of Decision-making Systems, Personal Digital Traces, and Data Integration. Her recent public scholarship work on explaining the NYC School Admission lottery process to families, in collaboration with elected parent representatives, was instrumental in increasing transparency and accountability in the NYC high school application system and received an award from the NYC Citywide Council on High Schools recognizing leadership and service on behalf of New York City Public School Families in April 2024. Amélie received her Ph.D. in Computer Science from Columbia University in 2005. She is the recipient of a Microsoft Live Labs Award, three Google Research Awards, and an NSF CAREER award. Speaker: Abstract: Algorithmic systems and data processes are being deployed to aid a wide range of high-impact decisions: from school applications or job interviews to gathering, storing, and analyzing personal data, or even performing critical tasks in the electoral process. These systems can have momentous consequences for the people they affect but their internal behaviors are often incompletely communicated to stakeholders, leaving them frustrated and distrusting of the outcomes of the decisions. Transparency and accountability are critical prerequisites for building trust in the results of decisions and guaranteeing fair and equitable outcomes.In this talk, I will present my work on making these opaque processes more transparent and accountable to the public in several real-world applications. In particular, I will discuss how ranking aggregation functions traditionally used in decision systems inadequately reflect the intention of the decision-makers and present work on providing transparent metrics to clarify the ranking process. In addition, ranking functions that are used in resource allocation systems often produce disparate results because of bias in the underlying data, I will show how compensatory bonus points can transparently address disparate outcomes in ranking applications. Furthermore, real-world deployments of algorithmic decision-making solutions often run into implementation constraints that impact the guarantees of the underlying algorithms, I will discuss practical challenges associated with algorithms used in the electoral process and their impacts on the trustworthiness of electoral outcomes. Organizations do not have strong incentives to explain and clarify their decision processes; however, stakeholders are not powerless and can strategically combine their efforts to push for more transparency. I will discuss the results and lessons learned from such an effort: a parent-led crowdsourcing campaign to increase transparency in the New York City school admission process. This work highlights the need for oversight and AI governance to improve the trust of stakeholders who have no choice but to interact with automated decision systems. Location: CoRE 301 Committee: |
Start Date: 12 Sep 2024; Start Time: 08:00PM - 09:30PM Title: Towards Synergy Between Reinforcement Learning and Generative Models Bio: Speaker: Abstract: Recent advances in reinforcement learning (RL) and generative models have led to groundbreaking achievements. However, both fields encounter significant challenges: RL methods often exhibit high sample complexity, while generative models frequently face misalignment with human preferences. This dissertation addresses these challenges by exploring the synergistic relationship between RL and generative models, and is structured into two main parts. The first part focuses on model-based reinforcement learning (MBRL), which enhances data efficiency for RL by incorporating a generative world model that can simulate the environment. We tackle two primary limitations of the leading MBRL agent, Dreamer. First, to address the short-range memory constraints of Dreamer's RNN-based world model, we introduce S4WM, the first world model framework that integrates the long-range memory capabilities of state space models. Second, to mitigate Dreamer's sensitivity to visual distractions caused by its reconstruction-based training, we develop a novel reconstruction-free MBRL agent called DreamerPro. The second part explores the potential of RL to improve generative models. We propose PRDP, a novel RL method for aligning diffusion models with human preferences. The stable large-scale training enabled by PRDP significantly enhances the quality of generated images on complex and unseen prompts. Location: CoRE 301 Committee: Prof. Sungjin Ahn (Chair) Prof. Vladimir Pavlovic Prof. Hao Wang Prof. Kimin Lee (External) |
Start Date: 17 Sep 2024; Start Time: 10:30AM - 12:00AM Title: Efficient Query Processing of Large-Scale Unstructured Data Bio: Dong Deng is an Assistant Professor in the Department of Computer Science at Rutgers University. Before joining Rutgers, he was a postdoc in the Database Group at MIT, where he worked with Mike Stonebraker and Sam Madden on data curation systems. He obtained his Ph.D. in Computer Science from Tsinghua University. His research interests include large-scale data management, vector databases, data science, data curation, and database systems. He has published over 50 research papers in top database venues, including SIGMOD, VLDB, and ICDE. His research is supported by the National Science Foundation, Adobe, and The ASSISTments Foundation. Speaker: Abstract: Large-scale unstructured data, such as vectors and texts, are ubiquitous nowadays due to the rapid development of deep learning and large language models. Many machine learning models have been developed to effectively represent real-world objects as high-dimensional feature vectors. Meanwhile, real-world objects (e.g., products, video frames) are often associated with structured attributes (e.g., price, timestamp). In many scenarios, both the feature vectors and the structured attributes of these objects need to be jointly queried. In this talk, I will present our recent work on multi-modal approximate nearest neighbor search, which finds the approximate nearest neighbors of a query vector while applying predicates to the structured attributes. Additionally, near-duplicate text alignment identifies snippets in a collection of long texts that are similar to a short query text. This computation intensive operation has applications in bioinformatics, large language model evaluation, and copyright protection. I will report on our recent progress in efficient near-duplicate text alignment over large-scale text corpora, such as the training data of large language models. Location: CoRE 301 Committee: |
Start Date: 20 Sep 2024; Start Time: 12:00PM - 04:00PM Title: Computer Science Department Undergraduate Fall Fair Bio: Speaker: Abstract: Location: Busch Student Center -BSC Center Hall Committee: |
Start Date: 20 Sep 2024; Start Time: 01:00PM - 03:00PM Title: Advancements in Modeling Crowd Navigation from Cognition to Simulation to Prediction Bio: Speaker: Abstract: This dissertation advances the intersection of spatial cognition, crowd simulation, crowd flow prediction, and human trajectory prediction, aiming to develop more realistic and efficient models for autonomous systems. The research emphasizes the importance of grounding models in cognitive principles to accurately model human behavior. This approach not only enhances the realism of simulations, but also provides valuable insights for designing safer and more efficient public spaces. However, behavioral realism comes at a prohibitively expensive computational cost. This body of work introduces and significantly improves a novel framework that circumvents this scalability issue by performing long-term crowd flow prediction (LTCFP), transforming the microscopic simulation problem into a macroscopic image-to-image regression problem. We have made foundational contributions to this novel problem in synthetic data generation, feature extraction, modeling, and evaluation. Furthermore, the same cognitive principles that have been used to improve simulation models have proven effective for significantly enhancing the accuracy of LTCFP models. Complementing this macroscopic problem formulation, there is a preexisting microscopic problem known as human trajectory prediction (HTP), which has not yet been operationalized for the same scale of crowds as LTCFP. This dissertation presents new evaluation metrics and datasets to assess the performance of state-of-the-art HTP models, highlighting their limited robustness despite having more specificity than LTCFP models. Location: CBIM 22 Committee: Prof. Mubbasir Kapadia Prof. Vladimir Pavlovic Prof. Mridul Aanjaneya Prof. Dinesh Manocha (External Member) |
Start Date: 23 Sep 2024; Start Time: 09:00AM - 10:30AM Title: Balancing Efficiency and Experience: A Predictive Cyber Physical System (CPS) for Urban Logistics Bio: Speaker: Abstract: Cyber-Physical Systems (CPS) integrate physical entities with information systems, enabling sensing, decision-making, and control actions, which has driven the development of Intelligent Logistics. Although research has made strides in technological advancements and optimization algorithms, the development of comprehensive Performance Assessment frameworks—critical for evaluating and advancing these innovations—remains underexplored, often relying on limited or isolated metrics.This dissertation addresses this gap by assessing performance across three key dimensions: efficiency, user experience, and their interactions. Efficiency examines operational speed and resource utilization, while user experience highlights ease of use and service quality. Analyzing the dynamic interplay between these two helps find an optimal balance between system performance and user satisfaction. Our key insight is that integrating external factors, such as real-time traffic and user feedback, allows the system to consider environmental factors beyond its internal constraints. Specifically, we introduce three core systems:i) AdaTrans, focused on efficiency, incorporates external records from other companies as environment detectors to improve real-time transportation time prediction for individual orders.ii) COCO+, centered on experience, integrates historical and real-time behaviors of couriers and customers to improve causes identification in canceled pickup orders.iii) AdaService, emphasizing interaction, assesses last-mile terminal station performance, uncovering strategies to balance efficiency and service quality across varying operational conditions.These systems were tested with real-world data from a real-world logistics company. The results reveal that integrating external feedback and their interactions transforms the evaluation of logistics performance, surpassing state-of-the-art methods across diverse real-world scenarios. Location: CoRE 305 Committee: Prof.Desheng Zhang (Advisor), Rutgers CS Graduate Faculty Prof.Yongfeng Zhang, Rutgers CS Graduate Faculty Prof.Dong Deng, Rutgers CS Graduate Faculty Prof.Fei Miao, University of Connecticut, Pratt & Whitney Endowed Associate Professor |
Start Date: 24 Sep 2024; Start Time: 10:30AM - 12:00PM Title: Cross-Layered OS Design for Managing Heterogeneity in Modern Datacenters Bio: Sudarsun Kannan is an Assistant Professor in the Computer Science Department at Rutgers University. His research focuses on operating system design and its intersection with computer architecture, distributed systems, and high-performance computing (HPC) systems. His work has been published in top venues such as ASPLOS, OSDI, and FAST, and he has received best paper awards at SOSP and ASPLOS, along with the Google Research Scholar award. He co-chaired the HotStorage'22 workshop and serves as an Associate Editor for ACM Transactions on Storage. Speaker: Abstract: Modern datacenters increasingly rely on heterogeneous architectures to manage data growth, enhance performance, optimize resource utilization, and reduce energy costs. In this talk, I will present our work on operating systems designed to address extreme memory and storage heterogeneity. I will emphasize the importance of a cross-layered OS design philosophy that distributes responsibilities across runtimes, firmware, and hardware controllers. This approach promotes collaborative data processing and enhances scalability, performance, and resource efficiency, while maintaining the data reliability and isolation guarantees of traditional monolithic OS designs.To demonstrate the potential of this cross-layered approach, I will discuss its application in managing near-storage accelerators and redesigning OS architectures for storage heterogeneity. Additionally, I will explore cross-layered management of both fast and slow memory technologies. Finally, I will provide a brief overview of our ongoing work in developing cross-layered systems for sustainability and improving natural hazard detection systems. Location: CoRE 301 Committee: |
Start Date: 25 Sep 2024; Start Time: 10:00AM - 12:00PM Title: Practical Methods for Fair and Explainable Decision Making Bio: Speaker: Abstract: Algorithmic decision making is used to make a wide variety of important decisions in today’s society, from bail decisions to school matchings. There is an increasing recognition of the importance of understanding exactly how algorithms make their decisions. This dissertation aims at bridging the gap between algorithm designers and stakeholders by providing metrics and tools to better understand the behavior of decision processes. Bridging this gap has the potential to empower stakeholders to make more informed decisions about how they interact with the algorithms and increase their trust in these systems that are increasingly critical to the running of society. For regular people to be full participants in algorithmic decision making, the algorithms chosen must be explainable and transparent so that no expert knowledge is required to understand their outcomes. The users of decision systems must also feel the algorithms that drastically affect the course of their lives are fair and reasonable. To further these explainability and fairness goals, this dissertation proposes explainable algorithms and metrics to promote decisions that are clearly fair and reasonable to the people they most affect.The first stage of algorithmic decision making is when decision makers choose the decision model to be used as an input to the algorithmic decision process; in many scenarios, decisions are based on ranking functions that aim at ordering participants to the decision. This dissertation provides explainable metrics to help the designers understand the diversity, fairness, and imputed weights of the developing ranking function. These metrics do not require expert knowledge to understand what they are measuring and how they are measuring it. By providing explainable metrics, decision makers can more easily trust the claims the metrics are making about the data. Specifically, this dissertation proposes transparent participation metrics to clarify the ranking process, by assessing the contribution of each parameter used in the ranking function in the creation of the final ranked outcome, using information about the ranking functions themselves, as well as observations of the underlying distributions of the parameter values involved in the ranking. In order to evaluate the outcome of the ranking process, diversity and disparity metrics are proposed to measure how similar the selected objects are to each other, and to the underlying data distribution. Metrics are evaluated on synthetic data, as well as on two real-world scenarios: high school admissions and decathlon scoring.Once explainable metrics are used in the design process, decision makers may want to automatically optimize the metrics without compromising the explainability of the outcome of the decision process. One such explainable metric is the disparity, which is closely related to the popular statistical parity measure of fairness. Optimizing this metric usually means minimizing the disparity between the population and the selected set. Traditionally, this would be done by minimizing disparity through an opaque transformation of the ranking functions or a set-aside system, in academic proposals about how to rank with fairness constraints and real-world school matching systems respectively. The same minimization can be done with bonus points without substantially increasing the complexity of the ranking function. Fairness goals are often added on top of an existing ranking function. By mirroring the language in which these ranking of functions are usually described, the fairness goals can be easily combined with the existing ranking function without reducing explainability. The conversion of the fairness goals into a specific number of bonus points is provided by a novel algorithm named the Disparity Compensation Algorithm(DCA). DCA uses a sampling-based approach modeled after Stochastic Gradient Descent to satisfy fairness goals orders of magnitude faster than competing algorithms and allows algorithm designers to accomplish fairness goals without compromising the explainability of the overall ranking function.The need for fairness and explainability can continue past the main part of the algorithmic decision process to the follow-up decisions that need to be made to respond to potential errors. Once an error has been detected, the outcome may need to be adjusted to avoid unfairly disadvantaging any participants due to the error. Adjusting the outcome to repair errors after the algorithm has already been completed needs a stronger explanation than simply running the algorithm as originally planned with no errors involved. Without this explanation, it can be difficult to convince both the harmed and unharmed participants that they are being treated fairly. A real-world example of this challenge arises in applications of deferred-acceptance (DA) matching algorithms, where errors or changes to the matching inputs are sometimes discovered only after the algorithm has been run and the results are announced to participants. Mitigating the effects of errors is a different technical problem than the original match since the decision-makers are often constrained by the decisions already announced. This dissertation proposes models for this new problem, along with explainable mitigation strategies to go with these models. Three different error scenarios are explored: In the first scenario, one of the participants is removed after the match is complete, leading the group matched to that participant unmatched. In the second scenario, some participants are unfairly disregarded and not ranked by a participant on the other side. In the last scenario, some participants are unfairly promoted over others. For each error type, the expected number of participants directly harmed, or helped, by the error, the number indirectly harmed or helped, and the number of participants with justified envy due to the errors are calculated. Error mitigation strategies must then arbitrate between minimizing the extra resources needed to mitigate the error and ensuring that no participants are unnecessarily harmed by the error. This dissertation provides algorithms, metrics, and models for fairer and more explainable algorithmic decision making. In particular, by providing metrics to help design ranking functions, explainable optimization, and sound error mitigation, this dissertation will allow for greater stakeholder participation in algorithmic decisions. As algorithms become increasingly cryptic it is essential to remember that key decision algorithms are designed to help humans make decisions at scale. If the algorithms are not fair and explainable to the humans they represent, they will not be successful no matter how effective they are. When explainability and fairness are centered, the algorithms can become natural extensions of the humans making the decisions. Location: CoRE 305 Committee: Professor Amélie Marian (chair) Professor David M. Pennock Professor Yongfeng Zhang Professor Nikhil Garg (External Member) |
Start Date: 01 Oct 2024; Start Time: 12:30PM - 02:00PM Title: The Median Procedure – a Universal Aggregation Rule? Bio: William S. Zwicker. Union College Mathematics Department and Murat Sertel Center for Advanced Economic Studies. Speaker: Abstract: The median procedure MP (Barthélemy and Monjardet, 1981) aggregates a sequence of binary relations from some input class I into a single relation (with ties allowed) in some output class O. Varying the choice of I and O gives rise to a remarkable range of known rules as special cases of MP, including:(1) Plurality voting,(2) Approval voting,(3) Kemeny voting,(4) Borda voting (with outcome a winner), (5) Mirkin aggregation of equivalence relations (a form of cluster analysis),but not (6) Borda voting (with outcome a ranking),(7) The Mean Rule (Duddy and Piggins),(8) j,k-Kemeny (a version of Kemeny for weak orders), or(9) Any of the known Condorcet extensions: Copeland, minimax, etc.MP is usually defined by choosing the relation in O "closest" (using a form of Hamming distance) to the inputs. But an alternative formulation using inner (aka, "dot") product and orthogonal decomposition is better equipped to explain how and why computational complexity varies among the rules listed above, and why rules (6), (7) and (8) – but not (9) – also arise from MP when an extra projection step is inserted. This formulation suggests that rules (1) - (8) all aggregate information in essentially the same way, but differ with regard to which dimensions of information are taken into account. Location: CoRE 301 Committee: |
Start Date: 10 Oct 2024; Start Time: 12:30PM - 02:00PM Title: Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis Bio: Mingyu Guo is a Senior Lecturer in the School of Computer and Mathematical Sciences at the University of Adelaide, Australia. He received his Ph.D. degree in Computer Science from Duke University, USA. Prior to joining the University of Adelaide, he was a Lecturer in the Economics and Computation group at University of Liverpool, UK. His main research focus is algorithmic game theory and its applications, as well as combinatorial optimization. Speaker: Abstract: We study worst-case VCG redistribution mechanism design for the public project problem. We use a multilayer perceptron (MLP) with ReLU activation to model the payment function and use mixed integer programming (MIP) to solve for the worst-case type profiles that maximally violate the mechanism design constraints. We collect these worst-case type profiles and use them as training samples to train toward better worst-case mechanisms. In practice, we require a tiny network structure for the above approach to scale. The Lottery Ticket Hypothesis states that a large network is likely to contain a "winning ticket" -- a much smaller subnetwork that "won the initialization lottery", which makes its training particularly effective. Motivated by this hypothesis, we train a large network and prune it into a tiny subnetwork. We run MIP-based worst-case training on the drawn subnetwork and evaluate the resulting mechanism's worst-case performance. If the subnetwork does not achieve good worst-case performance, then we record the type profiles that cause the current draw to be bad. To draw again, we restore the large network to its initial weights and prune using recorded type profiles from earlier draws, therefore avoiding drawing the same ticket twice. We expect to eventually encounter a tiny subnetwork that leads to effective training for our worst-case mechanism design task. Lastly, a by-product of multiple ticket draws is an ensemble of mechanisms with different worst cases, which improves the worst-case performance further. Using our approach, we find previously unknown optimal mechanisms for up to 5 agents. Our results confirm the tightness of existing theoretical upper bounds. For up to 20 agents, we derive significantly improved worst-case mechanisms, surpassing a long list of existing manual results.This paper mainly proposes a technique for designing neural networks for "worst-case" objectives. Specifically, I use this neural networks based technique to design worst-case optimal mechanisms. The talk is based on this paper published in AAAI-24 https://arxiv.org/abs/2305.11011 Location: CoRE 301 Committee: |
Start Date: 15 Oct 2024; Start Time: 10:30AM - 12:00PM Title: Mechanistic Interpretability and AI's Safety Bio: Zining Zhu is an assistant professor at the Stevens Institute of Technology. He received PhD degree at the University of Toronto and Vector Institute in 2024. He is interested in understanding the mechanisms and abilities of neural network AI systems, and incorporating the findings into controlling the AIs. In the long term, he looks forward to empowering real-world applications with safe and trustworthy AIs that can collaborate with humans. Speaker: Abstract: Recently, LLMs have demonstrated incredible capabilities, leading to concerns about their safety. In this presentation, I argue that one way towards safety is via understanding and controlling the mechanics of LLMs. I will briefly review some most promising mechanisms along some different granularity levels: representation, module, and neuron. I will present some of our lab’s works along each of the granularity levels, and how I consider the future mechanistic interpretability research will benefit AI safety. Location: CoRE 301 Committee: |
Start Date: 18 Oct 2024; Start Time: 01:00PM - 02:00PM Title: Towards Adaptive and Evolving Systems Software Bio: Sanidhya Kashyap is a systems researcher and an Assistant Professor at the School of Computer and Communication Sciences at EPFL. His research focuses on designing robust and scalable systems software. He received the Vmware Early Career Faculty Award in 2021 and his Ph.D. from Georgia Tech in 2020. Speaker: Abstract: Specializing the OS for application requirements is becoming the need of the hour. In this talk, I will present our ongoing effort to meet these requirements dynamically. First, I will present a new approach to designing a storage stack that allows file system developers to design userspace file systems without compromising file system security guarantees while at the same time ensuring direct access to non-volatile memory (NVM) hardware. I will present a new file system architecture that decouples file system design, access control, and metadata integrity enforcement, providing a clean structure to design file systems. Then, I will present KFlex, a new approach to kernel extensibility that balances expressivity and performance. KFlex separates the safety of kernel-owned resources (e.g., kernel memory) from the safety of extension-specific resources (e.g., extension memory). This separation enables KFlex to use distinct, bespoke mechanisms to enforce each safety property, which enables the offload of diverse functionality while incurring low runtime overheads. Location: CoRE 301 Committee: |
Start Date: 29 Oct 2024; Start Time: 10:30AM - 11:30AM Title: Towards a Science of Human-AI Teams Bio: Valerie is a Machine Learning Ph.D. student at Carnegie Mellon University. Her research aims to improve human-AI interactions through a use-case-grounded lens and to leverage insights from practical user studies to design new interactive systems. Her research sits at the intersection of ML, NLP, and HCI. Valerie is a recipient of the NSF Graduate Research Fellowship, a former intern at MSR’s Fairness, Accountability, Transparency & Ethics in AI group, and a Rising Star in Data Science. Valerie completed her B.S. in Computer Science at Yale University. Speaker: Abstract: AI models have the potential to support and complement human decision-makers and users. And yet, the deployment of human-AI teams still faces practical challenges. I’m interested in developing a more principled workflow for building human-AI teams. In particular, this talk will focus on answering two questions: (1) what the right evaluation paradigms are to measure team performance, and (2) what are interaction mechanisms that can facilitate the appropriate usage of AI support. I will discuss how existing ML/NLP literature has attempted to answer each of these questions, their limitations, and promising alternatives. Location: CoRE 301 Committee: |
Start Date: 31 Oct 2024; Start Time: 01:00PM - 02:30PM Title: White-Box Optimization Approaches for Ultra-Large-Capacity NAND Flash-Based SSDs Bio: Jisung Park is an Assistant Professor in the Department of Computer Science and Technology at POSTECH, where he leads the Computer Architecture and Operating Systems (CAOS) Laboratory. Jisung is also affiliated with the Graduate School of Artificial Intelligence. Before joining POSTECH in 2022, Jisung spent three years working as a Senior Researcher and Lecturer in the Department of Information Technology and Electrical Engineering at ETH Zürich. Jisung earned his Ph.D. degree in Electrical Engineering and Computer Science and B.E. degree in Computer Science and Engineering from Seoul National University. Jisung's research interests span a wide range of computer systems fields, including computer architecture, system software, and embedded systems, with a special focus on memory and storage systems, system security, and HW/SW cooperation. Speaker: Abstract: This talk discusses potential challenges in designing ultra-large-capacity NAND flash-based SSDs and introduces two white-box optimization approaches to address the challenges. NAND flash memory is the predominant technology for modern storage systems to meet the high-performance and large-capacity storage requirements of data-intensive applications. As a promising solution to reduce the total cost of ownership (TCO) of storage systems, there is increasing demand for ultra-large-capacity SSDs that offer unprecedented single-device storage capacity (e.g., 128 TB). Even though some manufacturers have recently introduced their successful development of such large-capacity SSDs, there exist new technical challenges that need to be addressed to achieve high I/O performance and long SSD lifetime, which primarily originate from the reliability issues of high-density NAND flash memory. In this talk, I will present two recent works, each of which effectively improves the performance and lifetime of high-density NAND flash-based SSDs, respectively, based on a deep understanding of underlying hardware components. Such white-box optimization approaches can effectively overcome the limitations of conventional black-box approaches, unlocking the full potential of NAND flash memory. First, I will introduce RiF (Retry-in-Flash), an in-flash processing technique to identify a read failure inside a NAND flash chip, which can avoid the waste of SSD-internal bandwidth due to read retry. Second, I will present AERO (Adaptive ERase Operation), which dynamically adjusts the erase latency to be just enough for reliable operation, thereby enhancing SSD lifetime by minimizing the erase-induced cell stress. Location: CoRE 301 Committee: |
Start Date: 04 Nov 2024; Start Time: 12:30PM - 02:00PM Title: From Algorithmic and RL-based to LLM-powered Agents Bio: Bo An is a President’s Chair Professor at Nanyang Technological University, Singapore. He received the Ph.D degree in Computer Science from the University of Massachusetts, Amherst. His current research interests include artificial intelligence, multiagent systems, computational game theory, and reinforcement learning. Dr. An was the recipient of the 2010 IFAAMAS Victor Lesser Distinguished Dissertation Award, an Operational Excellence Award from the Commander, First Coast Guard District of the United States, the 2012 INFORMS Daniel H. Wagner Prize for Excellence in Operations Research Practice, 2018 Nanyang Research Award (Young Investigator), and 2022 Nanyang Research Award. His publications won the Best Innovative Application Paper Award at AAMAS’12, the Innovative Application Award at IAAI’16, and the best paper award at DAI’20. He was invited to give Early Career Spotlight talk at IJCAI’17. He led the team HogRider which won the 2017 Microsoft Collaborative AI Challenge. He was named to IEEE Intelligent Systems' "AI's 10 to Watch" list for 2018. He was PC Co-Chair of AAMAS’20 and General Co-Chair of AAMAS’23. He will be PC Chair of IJCAI’27. He is a member of the editorial board of JAIR and is the Associate Editor of AIJ, JAAMAS, IEEE Intelligent Systems, ACM TAAS, and ACM TIST. He was elected to the board of directors of IFAAMAS, senior member of AAAI, and Distinguished member of ACM. Speaker: Abstract: In the early days of tackling AI problems involving complex cooperation and strategic interactions, algorithmic approaches were widely employed. Reinforcement learning has since proven effective in learning efficient policies for large-scale optimization problems that are beyond the scalability of traditional algorithmic approaches. Recently, the use of large language models (LLMs) as computational engines has given rise to a new paradigm: LLM-powered agents capable of addressing complex problems across various domains. This talk will explore our recent work within these three paradigms and offer insights into the development of scalable, efficient, and distributed artificial general intelligence. Location: CoRE 301 Committee: |
Start Date: 05 Nov 2024; Start Time: 02:20PM - 03:20PM Title: Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL. Bio: Speaker: Abstract: We study a novel information-theoretic query model, the query-with-sketch model, and its lower bounds. As an application, we obtain a barrier in derandomizing BPL.The query-with-sketch model extends the traditional query model by incorporating an agent that provides the algorithm with a short sketch of the input. The trade-off between the length of the sketch and the query complexity of the algorithm becomes interesting. Specifically, we establish a lower bound in this model for the Approximate Matrix Powering (AMP) problem, showing that, in a recursive generalization of the query-with-sketch model, AMP requires either polynomial query complexity or superpolynomial sketch length.Derandomizing BPL has long been a central question in complexity theory. Building on foundational results from [Nis92] and [SZ99], significant efforts have aimed to prove BPL = L. Currently, the best-known derandomization approach places BPL within SPACE(\log^{3/2}n/\sqrt{\log\log n}). Our lower bound above implies that, fully derandomizing BPL cannot rely on a natural, recursive use of approximated intermediate powers. Location: CoRE 431 Committee: Professor Jie Gao Professor Sumegha Garg Professor Roie Levin Professor Periklis A. Papakonstantinou Professor Michael E. Saks |
Start Date: 08 Nov 2024; Start Time: 10:00AM - 11:30AM Title: Informed Group Decision Making via Voting Bio: Speaker: Abstract: In our fast-paced, engaged, polarized, and increasingly on-line world full of both misinformation campaigns and conspiracy theories, there is an emerging public need for informed, fair, efficient, and incentive-aware group decisions in uncertain environments. Leveraging the wisdom of the crowd, we see voting as a powerful tool to solve this problem. Specifically, we would like to focus on scenarios where agents are strategic. Previous work has shown that an informed decision (a decision be made if there is no uncertainty) can still be reached with high probability in the equilibrium. We would like to take steps further in this topic, including discovering representation of knowledge and preferences, analyzing different voting rules and aggregation mechanisms, and balancing between accuracy and simplicity in the votes. Location: CoRE 305 Committee: Professor Lirong Xia Professor David Pennock Assistant Kangning Wang Assistant Professor Minsung Kim |
Start Date: 12 Nov 2024; Start Time: 12:30PM - 02:00PM Title: Speculative Denial-of-Service Attacks in Ethereum Bio: Aviv Zohar is a researcher in blockchain and distributed systems, focusing on the security, scalability, and economics of decentralized systems. He is a professor at the Hebrew University of Jerusalem since 2012, and is now spending a sabbatical year at Princeton. Speaker: Abstract: In blockchain environments, transaction validation is often performed by thousands of computers, making the process resource-intensive. To prevent resource exhaustion, users are required to pay for the computational resources their transactions consume. The introduction of smart contracts adds another layer of complexity, as these contracts can involve expensive computations that need to be verified at a cost that is unknown in advance. In this talk, I will discuss how smart contracts create denial-of-service vulnerabilities that are challenging to mitigate in the blockchain context and how developments within Ethereum’s ecosystem have exacerbated this issue. The talk is designed to be accessible, requiring no prior knowledge of the subject.The talk is based on joint work with Aviv Yaish, Kaihua Qin, Liyi Zhou, and Arthur Gervais. Location: CoRE 301 Committee: |
Start Date: 13 Nov 2024; Start Time: 03:15PM - 04:30PM Title: Towards Generalist Medical Artificial Intelligence: Model, Data, Knowledge and Beyond Bio: Speaker: Abstract: Artificial intelligence has demonstrated remarkable capabilities in processing and understanding diverse forms of data - analyzing images, comprehending language, recognizing speech, and interpreting complex patterns across multiple modalities. Despite these broad advances, healthcare remains a uniquely challenging domain where conventional AI approaches often fall short of clinical requirements. While current medical AI systems excel at specific tasks, they lack the generalist capabilities of human doctors who can interpret subtle patterns across diverse imaging modalities, reason about complex medical conditions, and generate comprehensive diagnostic reports. This gap is particularly evident given healthcare's distinct challenges: the need to interpret intricate anatomical patterns where errors can have serious clinical consequences, the scarcity of high-quality medical data due to privacy concerns and annotation costs, and the critical requirement to incorporate centuries of accumulated medical knowledge. This dissertation addresses these fundamental challenges through a comprehensive framework built on three interconnected pillars: Model, Data, and Knowledge. Our research evolves medical AI from narrow, task-specific solutions toward generalist models capable of handling diverse imaging modalities and diagnostic tasks simultaneously. By developing innovative architectural approaches, efficient learning strategies for limited data scenarios, and methods for integrating established medical expertise, we bridge the gap between pure data-driven approaches and clinical practice. The results demonstrate significant improvements in model generalization, data efficiency, and clinical relevance, marking a crucial step toward more reliable and versatile medical AI systems that can match the breadth of human doctors' capabilities. Location: CoRE 301 Committee: Professor Dimitris Metaxas (chair) Assistant Yongfeng Zhang Associate Professor Konstantinos Michmizos |
Start Date: 18 Nov 2024; Start Time: 10:00AM - 11:30AM Title: End-to-end Latency Measurement with One Side Traffic Visibility Bio: Speaker: Abstract: End-to-end latency is a crucial metric that indicates the performance of networked services deployed in data centers. User-experienced latency significantly impacts the revenue of online services like financial trading applications, online retail services, streaming services, and mobile computing. Therefore, tracking user-visible latency is a prime concern. Several factors, like network path congestion, server load fluctuations, and volatile traffic conditions, can impact latency experienced by users. As a result, there could be a high variance in latency over time. Therefore, tracking latency continuously over time without any additional overhead at all the components participating in service delivery is vital. Our work investigates passive and continuous measurement of user-visible latency for networked services by integrating measurements into vantage points between the client and server. The basic approach to measure latency is to determine the time between the departure of a client request and the arrival of its corresponding response at the vantage point. However, a key challenge in such measurement is that the vantage points of interest may only have the visibility of user traffic in one direction. For example, Load Balancers may be configured to handle request traffic but not response traffic. We introduce techniques to estimate the arrival time of a response by leveraging the closed-loop nature of network connections used by services. Further, we propose algorithms that exploit multiple observations over time to infer the user-experienced latency while observing only the request traffic. Experiments with web traffic of servers rendering websites under realistic server load show that our approach can achieve 98% accuracy relative to the direct estimation of the request-to-request latency and request-to-response latency at the client. Location: CoRE 431 Committee: Professor Srinivas Narayana Professor Badri Nath Professor Richard Martin Professor Mubbasir Kapadia |
Start Date: 22 Nov 2024; Start Time: 11:30AM - 01:00PM Title: Robots with Dynamics: Efficient Motion Planning and Analysis of Controllers via Machine Learning Bio: Speaker: Abstract: This thesis aims to improve the efficiency and robustness of motion planning for robots with significant dynamics, leveraging both advances in machine learning as well as contributions in algorithmic and foundational techniques. The key objectives are to (a) efficiently compute safe open-loop trajectories that obey non-trivial robot dynamics so that they are easy to follow with closed-loop controllers, and (b) efficiently analyze and characterize the capabilities of closed-loop robot controllers to enable safe real-world deployment.This effort starts by exploring alternatives to the standard methodology of generating control sequences in sampling-based planning for systems with dynamics. Typically, these methods rely on random controls, which are useful to argue desirable properties, but which lead to slow convergence and low-quality solutions in practice.To address this, the thesis first proposes using machine learning to train goal-reaching controllers via reinforcement learning. Such learned controllers can be integrated with sampling-based planners and help guide the expansion of the underlying planning structure towards the global goal. This is shown to lead to the faster discovery of high-quality trajectories on mobile robot navigation problems, including for physically-simulated challenges with uneven terrains.In addition, this thesis proposes the offline construction of a “roadmap with gaps” data structure for systems with dynamics, which can express the learned controller's reachability capabilities in a target environment. Online, the sampling-based planner uses the “roadmap with gaps” to promote the fact discovery of high-quality trajectories to the goal. The overall approach enhances the efficiency of motion planning in various benchmarks, including physics-based simulations of vehicular systems and aerial robots.The open-loop solutions generated by sampling-based planners require closed-loop feedback control for reliable real-world execution. To this end, the thesis first integrates techniques for identifying approximate analytical models of the robot's dynamics that allow fast motion planning and reduce the model gap. It then focuses on achieving closed-loop operation at both the planning and control levels by proposing a safe replanning framework for kinodynamic motion planning and integrating feedback controllers that reason about robot dynamics. These contributions allow for safe and efficient tracking of planned trajectories on a physical platform.Concurrently, the thesis also addresses the challenge of understanding the global dynamics of robot controllers, including learned ones, which is crucial for safe deployment of such solutions and the composition of controllers. A topological framework (Morse Graphs) is leveraged, and data-driven modeling approaches are proposed to enable data-efficient characterization of controller attractors and their regions of attraction, even for high-dimensional systems.Finally, the thesis contributes an open-source software library, which provides a flexible and efficient framework for integrating machine learning methods into kinodynamic planning and control. Location: SPR-402, 1 Spring St, New Brunswick Committee: Professor Kostas Bekris (Chair) Associate Professor Abdeslam Boularias Associate Professor Jingjin Yu Associate Professor Joydeep Biswas (external -- UT Austin). |
Start Date: 22 Nov 2024; Start Time: 02:00PM - 03:30PM Title: Learning to Reason with LLMs Bio: Noam Brown is a research scientist at OpenAI investigating reasoning and multi-agent AI. He co-created Libratus and Pluribus, the first AIs to defeat top humans in two-player no-limit poker and multiplayer no-limit poker, respectively, and Cicero, the first AI to achieve human-level performance in the natural language strategy game Diplomacy. He has received the Marvin Minsky Medal for Outstanding Achievements in AI, was named one of MIT Tech Review's 35 Innovators Under 35, and his work on Pluribus was named by Science as one of the top 10 scientific breakthroughs of 2019. Noam received his PhD from Carnegie Mellon University and his BA from Rutgers University. Speaker: Abstract: Large language models (LLMs) have demonstrated remarkable capabilities in generating coherent text and completing various natural language tasks. Nevertheless, their ability to perform complex, general reasoning has remained limited. In this talk, I will describe OpenAI's new o1 model, an LLM trained via reinforcement learning to generate a hidden chain of thought before its response. We have found that the performance of o1 consistently improves with more reinforcement learning compute and with more inference compute. o1 surpasses previous state-of-the-art models in a variety of benchmarks that require reasoning, including mathematics competitions, programming contests, and advanced science question sets. I will discuss the implications of scaling this paradigm even further. Location: CoRE 301 Committee: |
Start Date: 26 Nov 2024; Start Time: 09:00AM - 10:15AM Title: Neural Unsupervised Structure-Aware Representation Learning Bio: Speaker: Abstract: Although deep learning models have shown an impressive performance, they still lack in several important aspects such as robustness, systematic generalization, interpretability, reasoning, and the ability to create new knowledge from limited experience. To address these limitations, learning representations of data that capture its underlying hidden structure is thought to be crucial. This dissertation develops architectures and algorithms for learning structure-aware representations without any human supervision or labels, aiming to capture (1) the 4D spatiotemporal structure and (2) the compositional object-centric structure of visual scenes. In Part One, we learn the 4D spatiotemporal structure by integrating observations over time and employing predictive coding. This improves novel view synthesis over baselines, pointing to a superior representation of the underlying scene geometry and dynamics. In Part Two, we introduce a novel object-centric representation learning method by inverting a flexible decoder, demonstrating for the first time the ability to decompose complex scene images and render systematically novel images. We further extend this method to handle videos through two routes: a sequential route via recurrence and a parallelizable route via causal attention. In Part Three, we shift focus towards systematic generalization and concept reuse. We develop a novel method that not only disentangles objects but also learns intra-object factor concepts that are optimized for reusability across scenes. Lastly, we develop a novel image-to-image translation benchmark to measure the ability of deep learning models to generalize to systematically novel visual scenes. Location: CoRE 305 Committee: Professor Sungjin Ahn (Chair) Professor Hao Wang Professor Yongfeng Zhang |
Start Date: 03 Dec 2024; Start Time: 12:30PM - 02:00PM Title: Production, Consumption, Absorption, Impact of News Bio: David Rothschild is a Senior Principal Research and Economist at Microsoft Research. His work pushes the boundaries on varying data and methods: polling, prediction markets, social media and online data, large behavioral and administrative data, and large-language models. His work focuses on solving practical and interesting questions including: mapping and updating public opinion, the market for news, effect of advertising, behavioral economics and finance, an economist's take on public policy, and how AI is affecting all of this. Speaker: Abstract: In this talk, David will discuss an ongoing project using LLM and Human-in-the-Loop coding to label news in near-real time (https://mediabiasdetector.seas.upenn.edu/) And discuss key findings about what mainstream media chose to cover in 2024 and how that may have impacted the general voting population. Location: CoRE 301 Committee: |
Start Date: 06 Dec 2024; Start Time: 02:00PM - 04:00PM Title: Conceptual Explanations for Vision and Language Foundation Models Bio: Speaker: Abstract: Vision and language foundation models, such as Vision Transformers (ViTs) and Pretrained Language Models (PLMs), have seen significant advances due to their capability to process and understand visual and textual information. However, trustworthy and interpretable explanation methods for these models remain underdeveloped, especially in post-hoc conceptual explanations that span multiple modalities. Our work introduces a unified framework to generate conceptual explanations for vision and language models, addressing core desiderata, such as faithfulness and stability. Specifically, we introduce variational Bayesian conceptual explanation methods that model the latent distributions of visual/textual token embeddings, providing post-hoc explanations at the dataset, image, and patch levels. Our analysis reveals how modeling multi-level joint distributions of visual or language embeddings can offer interpretable insights, bridging the gap between vision-language model predictions and human-understandable concepts. Extensive experiments across various benchmarks demonstrate that our approach consistently outperforms existing explanation methods by meeting these desiderata and offering a comprehensive analysis of model predictions. Location: CoRE 305 Committee: Professor Hao Wang (Chair) Professor Dimitris Metaxas Professor Yongfeng Zhang Professor Sharon Levy |
Start Date: 12 Dec 2024; Start Time: 10:00AM - 12:00PM Title: Bridging the Gap Between High-Level Quantum Algorithms and Low-Level Quantum Assembly: Qubit Reuse and Compilation Optimization Bio: Speaker: Abstract: Despite the rapid advancements in quantum computing, practical implementation is hindered by challenges such as limited qubit resources, low fidelity, and error-prone operations. This dissertation presents a comprehensive exploration of quantum compilation and error mitigation through three key projects. First, the CaQR framework leverages mid-circuit measurements and qubit reuse to address qubit limitations, reducing resource constraints, and enhancing fidelity on real quantum hardware. Second, AutoBraid introduces compiler-level support for surface code error correction, enabling more efficient fault-tolerant quantum computation. Lastly, QASMTrans, an open-source quantum compiler, supports scalable algorithms like QAOA and achieves significant performance improvements across diverse quantum architectures. Together, these contributions bridge the gap between high-level quantum algorithms and low-level hardware, advancing scalable, efficient, and error-resilient quantum computing. This work lays the foundation for future research, pushing the boundaries of practical quantum computation. Location: CoRE 305 Committee: Associate Professor Eddy Z. Zhang Distinguished Professor Mario Szegedy Assistant Professor Yipeng Huang |
Start Date: 12 Dec 2024; Start Time: 01:00PM - 02:30PM Title: Tabletop Object Rearrangement: Structure, Complexity, and Efficient Combinatorial Search-Based Solutions Bio: Speaker: Abstract: This thesis provides an in-depth structural analysis and efficient algorithmic solutions for tabletop object rearrangement with overhand grasps (TORO), a foundational task in advancing intelligent robotic manipulation. Rearranging multiple objects in a confined workspace presents two primary challenges: sequencing actions to minimize pick-and-place operations—an NP-hard problem in TORO—and determining temporary object placements (“buffer poses”) within a cluttered environment, which is essential yet highly complex. For TORO with available external free space, this work investigates the minimum buffer space, or “running buffer size,” required for temporary relocations, presenting both theoretical insights and exact algorithms. For TORO without external free space, the concept of lazy buffer verification is introduced, with its efficiency evaluated across various manipulator configurations, including single-arm, dual-arm, and mobile manipulators. Location: SPR-402, 1 Spring St, New Brunswick Committee: Professor Jingjin Yu Professor Kostas Bekris Associate Professor Abdeslam Boularias Associate Professor Kaiyu Hang (external) |
Start Date: 13 Dec 2024; Start Time: 01:00PM - 02:30PM Title: Learning Differentiable Tensegrity Dynamics with Graph Neural Networks Bio: Speaker: Abstract: Tensegrity robots are composed of rigid struts and flexible cables. They constitute an emerging class of hybrid rigid-soft robotic systems and are promising systems for a wide array of applications, ranging from locomotion to assembly. They are difficult to control and model accurately, however, due to their compliance and high number of degrees of freedom. To address this issue, prior work has introduced a differentiable physics engine designed for tensegrity robots based on first principles. In contrast, this work proposes the use of graph neural networks to model contact dynamics over a graph representation of tensegrity robots, which leverages their natural graph-like cable connectivity between end caps of rigid rods. This learned simulator can accurately model 3-bar and 6-bar tensegrity robot dynamics in simulation-to-simulation experiments where MuJoCo is used as the ground truth. It can also achieve higher accuracy than the previous differentiable engine for a real 3-bar tensegrity robot, for which the robot state is only partially observable. When compared against direct applications of recent mesh-based graph neural network simulators, the proposed approach is computationally more efficient, both for training and inference, while achieving higher accuracy. Location: Room 402, 4th floor, 1 Spring Street, Downtown New Brunswick Committee: Assistant Professor Mridul Aanjaneya Professor Kostas Bekris Associate Professor Abdeslam Boularias Assistant Professor He Zhu |
Start Date: 16 Dec 2024; Start Time: 10:00AM - 11:30AM Title: Computational Modeling for Food Image and Video Understanding Bio: Speaker: Abstract: Although sophisticated computer vision models have excelled in numerous tasks, they often struggle with images or videos related to food, especially those depicting cooked meals or food preparation. The food domain presents numerous challenges due to factors such as hidden ingredients, alterations in the appearance of ingredients during cooking, and significant variability in images of dishes prepared with the same recipes. Moreover, cooking procedures frequently allow for interchangeable or potentially parallel sequences of steps, leading to significant variability in the videos depicting cooking. Therefore, designing computer vision models for applications involving food images and videos necessitates particular attention because of the domain’s inherent complexity.This dissertation focuses on computational modeling for both cooking images and videos. For images, we study the problem of predicting the relative amounts of the ingredients. We propose PITA framework leveraging retrieval features and Wasserstein distance to solve the problem. We show PITA significantly outperforms previous baselines. In the context of videos, we address the challenge of deriving an instruction flow graph for each video, which models sequencing as well as parallelism or interchangeability of the cooking steps. We propose Box2flow, which combines features from object detection and BERT to calculate pairwise edge probabilities. A spanning-tree algorithm is then used to predict the flow graph from edge probabilities for each video input. We show that Box2flow outperforms standard captioning-based methods.Our research paves the way for numerous important directions in future studies, particularly when integrated with Large Language Models. The methodologies developed here for food analysis are adaptable and could be utilized in broader computer science challenges involving complex datasets. Location: CBIM 22 Committee: Prof. Vladimir Pavlovic (chair) Prof. Yongfeng Zhang Prof. Hao Wang |
Start Date: 17 Dec 2024; Start Time: 10:00AM - 12:00PM Title: Enhancing Quantum Computing Efficiency: Compilation Strategies Leveraging Algorithmic and Hardware Insights Bio: Speaker: Abstract: Quantum computing has rapidly advanced, with diverse quantum devices such as superconducting qubits, trapped ions, neutral atoms, and photonic chips. Since Richard Feynman's 1981 proposal, significant algorithms—including Shor's algorithm, Grover's search, and Variational Quantum Algorithms (VQAs)—have been developed, underscoring the need for efficient systems that bridge high-level algorithms and hardware implementations. Quantum algorithms, typically expressed in high-level languages, are transformed into logical circuits, then mapped onto physical circuits using hardware-specific basis gates via qubit mapping and routing, and finally executed through control pulses. Future quantum systems are expected to incorporate error correction codes to enhance computational reliability.My research focuses on algorithm-specific compilation with cross-stack optimization to enhance the efficiency of quantum program execution on existing hardware. I explore optimization opportunities arising from gate commutativity in algorithms like the Quantum Approximate Optimization Algorithm (QAOA) and Quantum Fourier Transform (QFT), as well as flexibility in circuit synthesis for Variational Quantum Eigensolver (VQE) algorithms. Additionally, I analyze often-overlooked hardware characteristics, such as the regularity of qubit connectivity in modern quantum devices, to inform compilation strategies.By studying gate commutativity and qubit connectivity, we discovered a compilation pattern for QAOA achieving linear circuit depth for clique graphs. Building upon this, we developed a general framework adaptable to practical cases, effectively handling sparsity of problem graphs and hardware noise variability. This led to up to 72% reduction in circuit depth and 66% reduction in gate count on IBM and Google architectures with up to 1,024 qubits, outperforming baselines in experiments on IBM Mumbai.We extended this to QFT compilation, resulting in the first linear-depth QFT circuits for architectures like Google Sycamore, IBM heavy-hex, and 2D grids with arbitrary qubit counts. Our methods overcome limitations of techniques relying on SAT solvers or heuristics, which often suffer from long compilation times or suboptimal outcomes due to large search spaces.In another contribution, we introduced Tetris, a compilation framework for VQA applications. Tetris focuses on reducing two-qubit gates during compilation, as these have higher error rates and execution times. By exploiting opportunities in circuit synthesis and using a refined intermediate representation of Pauli strings, Tetris reduces two-qubit gate counts and mitigates hardware mapping costs through a fast bridging approach. Overall, Tetris achieves reductions of up to 41.3% in CNOT gate counts, 37.9% in circuit depth, and 42.6% in circuit duration across molecular simulations compared to state-of-the-art approaches.The methodologies and insights from my research are not limited to these three scenarios; they can be applied to future quantum program compilation tasks. By focusing on cross-stack optimization and leveraging both algorithmic properties and hardware characteristics, my work contributes to bridging the gap between quantum algorithms and hardware, significantly improving the efficiency and scalability of quantum computing implementations. Location: CoRE 305 Committee: Professor Zheng Zhang Professor Mario Szegedy Professor Yipeng Huang |
Start Date: 30 Jan 2025; Start Time: 01:30PM - 03:00PM Title: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches Bio: Speaker: Abstract: The near-duplicate text alignment search problem—aimed at identifying all near-duplicate passage pairs between a query document and a collection of source documents—presents a computationally intensive challenge. This task is crucial for applications like plagiarism detection and LLM memorization. Brute-force methods require comparing O(n^2 m^2) passage pairs between a single query document with n words and a single source document with m words, making them impractical for large corpora. Existing solutions often rely on heuristics like "seeding-extension-filter," which lack theoretical guarantees and involve numerous difficult-to-tune hyperparameters. A previous work ALLIGN employs min-hash sketches to solve this problem. However, it is limited to comparisons between pairs of documents.To address these limitations, we propose leveraging bottom-k sketching to estimate Jaccard similarity between passages. A key insight in our approach is that contiguous passages share the same bottom-k sketch. We introduce the concept of “compact window” to represent all passages that share the same sketch in a concise manner and develop an efficient algorithm to group these passages in O(nlogn+nk)time, reducing the total number of sketches from O(n^2) to O(nk) for a document with n words. Experimental results on real-world datasets demonstrate that our techniques achieve high efficiency.List of Publication(s):TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection (SIGMOD2022) Location: CoRE 305 Committee: Assistant Professor Dong Deng (Advisor) Associate Professor Yongfeng Zhang Assistant Professor He Zhu Assistant Professor Arpita Biswas |
Start Date: 04 Feb 2025; Start Time: 10:30AM - 12:00PM Title: On The Myths of Reasoning Language Models: What is Next? Bio: Dan Roth is the Eduardo D. Glandt Distinguished Professor at the Department of Computer and Information Science, University of Pennsylvania and the Chief AI Scientist at Oracle. Until June 2024 Dan was a VP/Distinguished Scientist at AWS AI. In his role at AWS Roth led over the last three years the scientific effort behind the first-generation Generative AI products from AWS, including Titan Models, Amazon Q efforts, and Bedrock, from inception until they became generally available. Dan is a Fellow of the AAAS, ACM, AAAI, and ACL. In 2017, Dan was awarded the John McCarthy Award; he was recognized for “for major conceptual and theoretical advances in the modeling of natural language understanding, machine learning, and reasoning.” He has published broadly in natural language processing, machine learning, knowledge representation and reasoning, and learning theory, was the Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR) and has served as a Program Chair and Conference Chair for the major conferences in his research areas. Roth has been involved in several startups; most recently he was a co-founder and chief scientist of NexLP, a startup that leverages the latest advances in Natural Language Processing, Cognitive Analytics, and Machine Learning in the legal and compliance domains. NexLP was acquired by Reveal. Dan received his B.A Summa cum laude in Mathematics from the Technion, Israel and his Ph.D. in Computer Science from Harvard University in 1995. Speaker: Abstract: The rapid progress made over the last few years in generating linguistically coherent natural language has blurred, in the mind of many, the difference between natural language generation, understanding, and the ability to reason with respect to the world. Nevertheless, robust support of high-level decisions that depend on natural language understanding, and one that requires dealing with “truthfulness” are still beyond our capabilities, partly since most of these tasks are computationally more complex than language models can support, are very sparse, often require grounding, and may depend on new types of supervision signals. I will discuss some of the challenges underlying reasoning and argue that we should focus on LLMs as orchestrators – coordinating and managing multiple models and special purpose agents. I will discuss some of the challenges and present some of our work in this space, focusing on supporting planning and a range of quantitative, visual, and spatial reasoning tasks. Location: CoRE 301 Committee: |
Start Date: 07 Feb 2025; Start Time: 04:00PM - 06:00PM Title: Controlling Long-Horizon Behavior in Reinforcement Learning Bio: Speaker: Abstract: Reinforcement learning (RL) has been successful in a very wide range of domains, from Atari games, to robotic control, to theorem proving. However, existing reinforcement learning methods tend to only work well over short time horizons -- many aspects of the problem become exponentially harder as time horizons grow. In particular, long time horizons make exploration and planning very challenging, and can worsen biases in some popular algorithms. In hard-exploration settings, standard algorithms like MCTS can take exponential or super-exponential time to explore the full environment. In model-based RL, predictions with a learned model may become exponentially worse as the time horizon increases. In the Hindsight Experience Replay algorithm (HER), biases from stochastic environments become worse over longer time horizons. The common problem underlying these issues is that local information available to the policy is not always sufficient to solve the problem -- global information about the state space must sometimes be made available to the agent to enable a efficient solution. This thesis aims to address these issues by developing mathematical tools for representing and controlling the long-horizon behavior of RL agents. In particular, focus is placed on the state occupancy measure and state successor measure. These tools are useful because they reduce RL to maximizing a linear objective with linear constraints. This means that many problems can be reformulated in a way that requires far less dependence on the time horizon. In a wide range of domains, I show that this tool can be used to address issues with convergence, exploration, and bias. Location: Room 402, 4th floor, 1 Spring Street, Downtown New Brunswick Committee: Associate Professor Abdeslam Boularias Assistant Professor Hao Wang Professor Kostas Bekris External member: Bo Yuan |
Start Date: 11 Feb 2025; Start Time: 10:30AM - 12:00PM Title: Our Journey Towards a Diverse Computing Program: What Worked, Where we Are, and What we have Learned Bio: Dr. Ana Paula Centeno is an Associate Teaching Professor in the Department of Computer Science at Rutgers, New Brunswick. She received her PhD in 2019 from Rutgers and as a teaching faculty at Rutgers, has been involved in research to understand the pathway blocks that impede student success in the computer science major. She has published papers on this topic, has been active with the Advancing Women in Computer Science (AWiCS) initiative, and has received the Rutgers Presidential Employee Excellence Recognition Award and the Provost’s Award for Excellence in STEM Diversity in 2023 and 2021, respectively. Speaker: Abstract: Women and individuals from underrepresented groups are significantly underrepresented in educational pathways and professional roles in computing. This imbalance not only reveals broader social inequities but also alters the viewpoints of both current and future technologists. These perspectives can lead to a lack of motivation or self-efficacy in academia and implicit hiring and algorithmic biases in the professional world.The underrepresentation of women and other marginalized groups presents a significant challenge. Addressing the barriers to entry and advancement in the field is essential for creating a more inclusive computing landscape that reflects and serves the needs of all people. I will discuss our work toward addressing these barriers at the computer science department at Rutgers - report the approaches that we implemented, starting Fall 2019, their outcomes, and the challenges faced throughout this journey's stage. More importantly, we show that the changes implemented in our program had a positive impact on both underrepresented groups and the overall student body. Location: CoRE 301 Committee: |