July 2024 - talks - lists.cs.princeton.edu

Yufei Zheng will present her FPO "Compact Algorithms for Measuring Network Performance" on August 22, 2024 at 12pm in CS 301.
by Gradinfo 25 Jul '24

25 Jul '24

Yufei Zheng will present her FPO "Compact Algorithms for Measuring Network Performance" on August 22, 2024 at 12pm in CS 301. The members of Yufei's committee are as follows: Examiners: Jennifer Rexford (adviser), Maria Apostolaki, and Mark Braverman Readers:Huacheng Yu and David Hay (The Hebrew University of Jerusalem) All are welcome to attend. Please see abstract below. Abstract: For network administrators, performance monitoring provides valuable insights into network quality and security. The emergence of programmable network devices makes it possible to measure performance metrics in the data plane, where packets fly by. Running measurement tasks directly in the data plane improves eciency, preserves user privacy, and enables the possibility of real-time actions based on the analysis. However, programmable data planes have limited memory size and memory accesses. Meanwhile, measuring performance metrics fundamentally requires a large amount of memory resources, as each packet must be processed relative to its predecessor in the same flow. This dissertation tackles the specific challenges that arise from running performance measurements with limited memory. The first part of this dissertation introduces new data-plane algorithms for monitoring two canonical performance metrics related to Transmission Control Protocol (TCP): delay and TCP packet reordering. • In measuring delay distribution, existing algorithms often exhibit bias against larger delays. We present fridges, a novel data structure that allows for the correction of the survivorship bias due to hash collisions. The main idea is to keep track of the probability p that a delay sample is collected, and count it as 1/p samples. Using multiple fridges together, we can further improve the accuracy by computing a weighted average of single-fridge estimators. • We present ecient algorithms for identifying IP prefixes with heavy packet reordering. First, we sample as many flows as possible, regardless of their sizes, but only for a short period at a time. Next, we separately monitor the large flows over long periods, in addition to the flow sampling. Both algorithms measure at the flow level, and aggregate statistics at the prefix level. Existing counter-based algorithms for identifying heavy-hitter flows could also be modified to measure performance metrics. However, many of such algorithms, despite of showing good empirical performance, lack theoretical guarantees. In the second part, we present the first formal analysis for the performance of one such algorithm, the Random Admission Policy (RAP). • We show that, for a highly skewed packet stream with k heavy flows, RAP with memory size k stores O(k) heavy flows with constant probability.

1 0

Linda Cai will present her FPO "Algorithmic Decision Making with Imperfect Information and Practical Irrationality" on August 7th, 2024 at 11am in CS 402.
by Gradinfo 19 Jul '24

19 Jul '24

Linda Cai will present her FPO "Algorithmic Decision Making with Imperfect Information and Practical Irrationality" on August 7th, 2024 at 11am in CS 402. Her FPO committee is as follows: Examiners: Matt Weinberg (adviser), Mark Braverman, and Huacheng Yu Readers: Bernard Chazelle and Brendan Lucier (Microsoft Research) Title and abstract follow below. All are welcome to attend. Title: Algorithmic Decision Making with Imperfect Information and Practical Irrationality Abstract: Market algorithms are ubiquitous in modern life, both online and offline. Historically, markets have been fundamental in matching supply with demand, where designers optimize regulations with global goals and participants optimize strategies with individual goals. Decision theory and mechanism design have evolved to study and prescribe the behavior and structure of these markets. This thesis addresses key questions at the intersection of market design and algorithmic decision-making: How do strategic decision-makers navigate choices, and how do resource producers allocate limited resources among strategic participants? The advent of information technology and increased data availability has revolutionized markets, enabling unprecedented scale, efficiency, and control. This development allows mechanism designers to create or modify market conditions, provided we understand their impact on the designer's objectives. In this thesis, we explore market algorithms in dynamic environments and under practical irrationality, analyzing how deviations from ideal models affect the utility of both designers and participants. We examine environmental changes such as market imbalance, resource augmentation, and competition faced by dominant sellers. For participants, we consider agents who are computationally bounded, behaviorally biased, or using learning algorithms. Our work aims to provide insights into the robustness and adaptability of market algorithms amid practical complexities and diverse participant behaviors.

1 0

Srikar Kasi will present his FPO "Quantum Decoding of Error Correction Codes for Wireless Networks" on Wednesday, August 7th, 2024 at 10am in CS 301 and Zoom.
by Gradinfo 16 Jul '24

16 Jul '24

Srikar Kasi will present his FPO "Quantum Decoding of Error Correction Codes for Wireless Networks" on Wednesday, August 7th, 2024 at 10am in CS 301 and Zoom. The members of his committee are as follows: Examiners: Kyle Jamieson (adviser), Margaret Martonosi, Yasaman Ghasempour Readers: Ravi Netravali, John Kaewell (InterDigital, Inc.), Paul Warburton (UCL) Location: CS 301, Zoom (https://princeton.zoom.us/j/5169139659) All are welcome to attend. Title: Quantum Decoding of Error Correction Codes for Wireless Networks Abstract: Error correction codes are essential for reliability and capacity in wireless networks. By correcting errors in real-time, they reduce re-transmissions, conserve bandwidth, and enhance network performance. However, these advantages come at the price of high decoding complexity and high latency which compels network designers to make sub-optimal deployment choices such as considering approximate decoding algorithms, limiting parallelism, bit-precision, and iteration counts, sacrificing the potential capacity and performance gains. Moreover, the ever-increasing user demand in wireless networks poses additional challenges in managing power consumption, operational costs, and the carbon footprint of base stations and terminals. This highlights the need for continued innovation in wireless network baseband architecture and implementation strategies. This dissertation introduces quantum computing-based processing architectures for decoding error correction codes, offering new computational paradigms to address these challenges at scale. By harnessing the principles of quantum mechanics, we propose a transformative shift in the way decoding is achieved, benefiting wireless performance and capacity, through the design and implementation of the following systems: (1) QBP, quantum annealing decoder for LDPC codes, (2) HyPD, hybrid classical--quantum annealing decoder for Polar codes, (3) QGateD, quantum amplitude amplification decoder for generic XOR-based error correction codes, (4) FDeQ, quantum gate decoder flexible to both LDPC and Polar codes, (5) QAVP, quantum annealing approach to vector perturbation precoding (a multi-user MIMO downlink baseband optimization problem). These systems collectively fall under the thesis that quantum computing is a promising approach for baseband processing, warranting further justification from an economic and environmental impact perspective. To address this and to make the case for quantum computing in wireless industry, (6) the dissertation presents a comprehensive cost and carbon footprint analysis of quantum hardware, both quantitatively and qualitatively. This may be of potential interest to NextG wireless networks and quantum architectures.

1 0

ECE Seminar: Daniel Genkin, July 16
by Emily C. Lawrence 11 Jul '24

11 Jul '24

ECE SEMINAR Speaker: Daniel Genkin, School of Cybersecurity and Privacy at Georgia Tech. Title: Side Channel Attacks: Lessons Learned or Troubles Ahead? Day: July 16, 2024 Time: 11:00am Location: B205 Engineering Quadrangle Hosts: David Wentzlaff Abstract : The security and architecture communities will remember the past five years as the era of side channels. Starting from Spectre and Meltdown, time and again we have seen how basic performance-improving features can be exploited to violate fundamental security guarantees. Making things worse, the rise of side channels points to a much larger problem, namely the presence of large gaps in the hardware-software execution contract on modern hardware. In this talk, I will give an overview of this gap, in terms of both security and performance. First, I will give a high-level survey on speculative execution attacks such as Spectre and Meltdown. I will then talk about how speculative attacks are still a threat to both kernel and browser isolation primitives, highlighting new issues on emerging architectures. Next, from the performance perspective, I will discuss new techniques for microarchitectural code optimizations, with an emphasis on compute-heavy workloads such as cryptographic protocols. Here I will show how seemingly simple, functionally equivalent, code modifications can lead to significant changes in the underlying microarchitectural behavior, resulting in dramatic performance improvements. The talk will be interactive and include attack demonstrations. Bio: Daniel Genkin is an Alan and Anne Taetle Early Career Associate Professor at the School of Cybersecurity and Privacy at Georgia Tech. Daniel’s research interests are in hardware and system security, with particular focus on side channel attacks and defenses. Daniel’s work has been recognized by best paper awards in multiple academic and industry venues, as well as covered by national and scientific press. Recently, Daniel has been part of the team performing the first analysis of speculative and transient execution, resulting in the discovery of Spectre, Meltdown and follow ups. Daniel has a PhD in Computer Science from the Technion Israel’s Institute of Technology and has been awarded the 2024 Alfred P. Sloan Research Fellowship.

1 0

Dingli Yu will present his FPO "Efficient Scaling of Large Models: Principles in Optimization and Data Aspects" on Thursday, July 18, 2024 at 1:30 PM in CS 402 and Zoom.
by gradinfo＠cs.princeton.edu 09 Jul '24

09 Jul '24

Dingli Yu will present his FPO "Efficient Scaling of Large Models: Principles in Optimization and Data Aspects" on Thursday, July 18, 2024 at 1:30 PM in CS 402 and Zoom. Location: Zoom link: https://princeton.zoom.us/j/7188314894?omn=99115109336 The members of Dingli's committee are as follows: Examiners: Sanjeev Arora (Adviser), Elad Hazan, Chi Jin Readers: Danqi Chen, Mark Braverman A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: Deep learning has advanced remarkably in recent decades. Yet, its theoretical foundations, particularly in the realm of large models, still lag behind. This thesis focuses on research that combines strong theoretical foundations with practical applications in efficiently scaling up large models. In the first part of the thesis, we focus on the training dynamics of neural nets by covering the theory of overparametrized neural nets. We will briefly introduce the theory of Neural Tangent Kernel (NTK), and proceed with Hyperparameter Transfer, an important application of the Tensor Program framework. We cover some of the earliest papers that establish NTK as a research field, along with the limitations of NTK. Hyperparameter Transfer is a novel and efficient paradigm for hyperparameter tuning by providing the optimal strategy for scaling up models. We introduce the characterization of the training dynamics for deep neural nets and offer an efficient hyperparameter selection scheme where optimal hyperparameters selected by tuning on shallow nets also work for deep nets. In the second part of the thesis, we focus on the data aspect of large model scaling. We will first introduce Skill-Mix, a novel and unique evaluation that sidesteps issues of traditional large language model (LLM) evaluations like data contamination and cramming for leaderboard. Skill-Mix randomly selects k language skills, then prompts the LLM to produce a concise text that demonstrates the chosen skills. The exponentially growing number of skill combinations provably prevent data contamination and can further reveal the novelty of successful answers by powerful LLMs. We then introduce ConceptMix, an extension of Skill-Mix to evaluate the capabilities of text-to-image models to combine k random selected visual concepts. Finally, we uncover the capabilities of LLMs to learn and generalize skill compositions given good responses from Skill-Mix. The results show that a few thousand of such data is enough to significantly improve the model performance in unseen skill combinations, beating models with much larger sizes. It suggests incorporating skill-rich synthetic text into training is an efficient way to scale up the data.

1 0