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

Kevin Qipeng Liu will present his FPO "Cryptography in the Age of Quantum Computers 2.0" on Tuesday, July 27, 2021 at 4PM via Zoom.
by jfarquer＠cs.princeton.edu 22 Jul '21

22 Jul '21

Kevin Qipeng Liu will present his FPO "Cryptography in the Age of Quantum Computers 2.0" on Tuesday, July 27, 2021 at 4PM via Zoom. Zoom link: https://princeton.zoom.us/j/6541841088 The members of Kevin's committee are as follows: Mark Zhandry (Adviser); Readers: Ran Raz and Gillat Kol; Examiners: Mark Braverman, Matthew Weinberg and Mark Zhandry. A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: People widely believe that full-scale quantum computers will eventually be viable in the near future. Quantum computers pose threats to many existing cryptosystems (most prominently, Shor's algorithm) while raising the possibility of using quantum[1]mechanical phenomena to achieve never-before-possible capabilities. First, I will present my work on quantum query complexity: I will show tight bounds for multi-collision finding problems and tight time-space tradeoffs for function inversion problems. The latter indicates that Grover's search cannot be sped up even with a piece of preprocessed quantum advice. This technique can be extended to prove the post-quantum non-uniform security of many existing cryptographic schemes. Second, I will present my work on post-quantum zero-knowledge proof. I will start by showing that post-quantum constant-round zero-knowledge protocols for NP with black-box simulators do not exist in the plain model unless NP is in BQP. Then, I will show how to achieve non-interactive zero-knowledge in the quantum random oracle model by proving that the famous Fiat-Shamir transformation is secure. Third, I will present my work on quantum copy-protection, which aims to use the unclonability of quantum states to achieve programs that cannot be copied. Towards this goal, I will show that any unlearnable function can be copy-protected relative to classical oracles. For specific cryptographic functionalities (such as signatures and RPFs), I will show that they can be copy-protected in the plain model.

1 0

Themistoklis Melissaris will present his FPO "Testing and Analyzing Correctness in Concurrent Systems: From Microprocessors to IoT and Distributed Systems" on Friday, July 30, 2021 at 12noon via Zoom.
by jfarquer＠cs.princeton.edu 20 Jul '21

20 Jul '21

Themistoklis Melissaris will present his FPO "Testing and Analyzing Correctness in Concurrent Systems: From Microprocessors to IoT and Distributed Systems" on Friday, July 30, 2021 at 12PM via Zoom. Zoom Link: https://princeton.zoom.us/j/98466211870 The members of his committee are as follows: Margaret Martonosi (Adviser); Kelly Shaw (Co-Adviser); Readers: Kyle Jamieson, Kelly Shaw (Williams College); Examiners: Wyatt Lloyd, David August, Margaret Martonosi. A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Applications such as the Internet of Things (IoT), multimedia streaming and self driving cars are drivers for explosive data growth. This data growth along with the slowdown of Moore's law presents new challenges for computing and spurs innovation for the next generation of hardware and software. To extract performance at manageable power, systems ranging from microprocessors to IoT devices and distributed systems increasingly leverage parallelism and concurrency. However, the performance and power benefits of parallelism come at the cost of increased complexity in designing, specifying and testing correctness of these systems. This dissertation draws insights across the domains of computer architecture, ΙοΤ and distributed systems, resulting in a set of practical tools and methodologies that allow for rigorous and efficient testing of correctness on multiprocessors, IoT systems and distributed systems. More specifically, this thesis introduces PerpLE, a tool that enables consistency testing for multiprocessors without per-iteration synchronization and relies on property based testing using litmus tests. This dissertation demonstrates how PerpLE speeds up testing performance by orders of magnitude against the state of the art, enabling fast error discovery in commercial microprocessors. Additionally, this dissertation presents Musli Tool, a practical tool for empirical consistency testing of distributed systems that leverages techniques and methodologies based on the computer architecture concept of litmus tests. Musli Tool automates testing by generating property-based tests and increases testing performance and fast portability in open source distributed systems. Finally, this thesis presents a study of rigorous concurrency testing on commercial and open source IoT systems. The study demonstrates correctness deficiencies of IoT systems and identifies the implications of race conditions, lack of atomicity and weak consistency on applications. To mitigate erroneous behavior for IoT applications, the OKAPI tool is introduced. This dissertation presents how to vastly improve the performance and efficiency of consistency testing by leveraging a synchronization free variant of litmus tests and by developing tools to enable analysis and generation of tests based on this new methodology. This thesis also demonstrates how to take lessons learned from testing correctness in microprocessors and adapting to other domains of concurrent systems, particularly distributed systems and IoT.

1 0

Orestis Plevrakis will present his FPO "New Exploration and Identification schemes for Linear Dynamics: the cases of Convex costs and Censored Data" on Thursday, July 22, 2021 at 1PM via Zoom.
by jfarquer＠cs.princeton.edu 15 Jul '21

15 Jul '21

Orestis Plevrakis will present his FPO "New Exploration and Identification schemes for Linear Dynamics: the cases of Convex costs and Censored Data" on Thursday, July 22, 2021 at 1PM via Zoom. Zoom link: <https://princeton.zoom.us/j/92035947506> https://princeton.zoom.us/j/92035947506 The members of Orestis' committee are as follows: Sanjeev Arora (Adviser); Readers: Chi Jin and Jason Lee; Examiners: Mark Braverman, Elad Hazan and Sanjeev Arora. A copy of his thesis is available upon request. Please email <mailto:gradinfo@cs.princeton.edu> gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract is as follows: Adaptive control, i.e., learning to control an unknown linear dynamical system, has a long history in statistics and control theory. However, sharp non-asymptotic bounds were only recently obtained, and are outputs of an ongoing research program aiming to apply tools from learning theory and optimization, to control theory. A common feature of all the major results of the program has been the learning-part of the proposed algorithms, i.e., the exploration strategy. All these algorithms apply the so-called "certainty-equivalence", where the learner spends the first steps applying random controls (e.g. Gaussian noise), then estimates the dynamics via least-squares, and thereafter optimizes the control-policy using these estimates. Even though this is the simplest exploration strategy, it is optimal for the classical linear quadratic regulator (LQR). In this thesis, I study 1) the problem of adaptive control when the cost can be any convex function (thus generalizing LQR), and 2) the problem of learning a linear dynamical system (LDS) from "censored" observations, i.e., the state is observed only when it falls inside some set (e.g., the state can be the position of an object and the set can be the camera-frame). For the first problem, certainty-equivalence is suboptimal. For the second, the least-squares solution is not even consistent. The contribution of the thesis is the development of new computationally and statistically efficient algorithms for both problems. Specifically, 1. For online control with convex costs, we consider the objective of regret vs. the class of disturbance-feedback-controllers. Leveraging ideas from convex geometry, we design an exploration strategy that achieves optimal regret, improving upon the previous best known bounds, which correspond to algorithms applying certainty-equivalence. 2. The problem of learning an LDS from censored observations was first considered by Lee and Maddala (1985), and Zeger and Brookmeyer (1986). We develop a new second order method: Stochastic Online Newton with Switching Gradients, building on the Online Newton Step of Hazan et al. (2007). This method is the first computationally and statistically efficient algorithm for this problem.

1 0

Alejandro Newell will present his Pre-FPO "Learning to solve structured vision problems" on Tuesday, July 20, 2021 at 2pm via Zoom.
by jfarquer＠cs.princeton.edu 13 Jul '21

13 Jul '21

Alejandro Newell will present his Pre-FPO "Learning to solve structured vision problems" on Tuesday, July 20, 2021 at 2pm via Zoom. Zoom Link: https://princeton.zoom.us/j/7228079201 Committee: Examiners: Jia Deng (Adviser), Adam Finkelstein, Felix Heide Readers: Olga Russakovsky, Szmon Rusinkiewicz All are welcome to attend. Title: Learning to solve structured vision problems Abstract: We want computer vision models to understand the rich world captured in images and video. This means not just recognizing objects, but seeing how they relate and interact. In the first half of my talk, I will present my work developing a general system for capturing visual relationships. Combining our contributions in both neural architecture and loss design, we enable deep models to express arbitrary semantic graphs. This allows models to connect parts of the image into structured outputs such as body parts into poses. These models outperform prior work in various challenging vision tasks. In the second half of the talk, I will cover ongoing work that moves beyond single images into video. Connections across time are often captured at the pixel level with optical flow. We show how to improve existing flow systems with feedback mechanisms inspired by self-supervised losses. I will also discuss future work extending such systems to downstream video tasks. Together, the presented body of work lays the foundations for systems that understand the world and its interactions across space and time.

1 0

Wei Hu will present his FPO "Understanding Deep Learning via Analyzing Dynamics of Gradient Descent" on Friday, July 23, 2021 at 9:30AM via zoom.
by jfarquer＠cs.princeton.edu 13 Jul '21

13 Jul '21

Wei Hu will present his FPO "Understanding Deep Learning via Analyzing Dynamics of Gradient Descent" on Friday, July 23, 2021 at 9:30AM via Zoom. Zoom link: https://princeton.zoom.us/j/2180408086 The members of Wei's committee are as follows: Sanjeev Arora (Adviser); Readers: Elad Hazan and Jason Lee; Examiners: Mark Braverman, Chi Jin and Sanjeev Arora. A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: The phenomenal successes of deep learning build upon the mysterious abilities of gradient-based optimization algorithms. Not only can these algorithms often successfully optimize complicated non-convex training objectives, but the solutions found can also generalize remarkably well to unseen test data despite significant over-parameterization of the models. Classical approaches in optimization and generalization theories that treat empirical risk minimization as a black box are insufficient to explain these mysteries in modern deep learning. This dissertation illustrates how we can make progress toward understanding optimization and generalization in deep learning by a more refined approach that opens the black box and analyzes the dynamics taken by the optimizer. In particular, we present several theoretical results that take into account the learning dynamics of the gradient descent algorithm. In the first part, we provide global convergence guarantees of gradient descent for training deep linear networks under various initialization schemes. Our results characterize the effect of width, depth and initialization on the speed of optimization. In addition, we identify an auto-balancing effect of gradient flow, which we prove to hold generally in homogeneous neural networks (including those with ReLU activation). In the second part, we study the implicit regularization induced by gradient descent, which is believed to be the key to mathematically understanding generalization in deep learning. We present results in both linear and non-linear neural networks, which characterize how gradient descent implicitly favors simple solutions. In the third part, we focus on the setting where neural networks are over-parameterized to have sufficiently large width. Through the connection to neural tangent kernels, we perform a fine-grained analysis of optimization and generalization, which explains several empirically observed phenomena. Built on these theoretical principles, we further design a new simple and effective method for training neural networks on noisily labeled data.

1 0

Raghuvansh Raj Saxena will present his FPO "Communication Complexity: For Coding, Commerce, and Currents" on Wednesday, July 21, 2021 at 12 noon via Zoom.
by jfarquer＠cs.princeton.edu 13 Jul '21

13 Jul '21

Raghuvansh Raj Saxena will present his FPO "Communication Complexity: For Coding, Commerce, and Currents" on Wednesday, July 21, 2021 at 12 noon via Zoom. Zoom Link: https://princeton.zoom.us/j/91504292936 The members of his Committee are as follows: Gillat Kol (Adviser); Readers: Matt Weinberg and Mark Braverman; Examiners: Ran Raz, Bernard Chazelle and Gillat Kol. A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Since its introduction in Yao's seminal paper [Yao79], communication complexity has revolutionized theoretical computer science. Indeed, not only has communication complexity been successful in areas where communication is an important resource, but it has also resulted in breakthroughs in areas that seemingly have nothing to do with communication! This is because bounds on communication can often be translated into bounds on other resources of interest, such as memory usage and circuit size. As the title suggests, we consider the role of communication complexity in the study of three different areas in theoretical computer science: Coding: Part I is about interactive error correcting codes, used to make interactive protocols resilient to noise. I study the noise tolerance of popular two-party and multi-party communication channels, constructing communication efficient codes with high noise tolerance for some of these channels, and proving that noise tolerance implies large communication overheads for others. Commerce: Part II studies communication problems in auction design, where the participating parties have their own interests and may not follow the protocol unless incentivized to do so. A common theme of this part is establishing tight separations between different classes of auctions, and understanding how various aspects of an auction affect its communication complexity. Currents: Part III covers my work on the memory requirement of graph streaming algorithms, which are algorithms whose input is a massive graph that they can only scan a few times. While algorithms that scan their input once are by now well understood, the situation is different for multi-pass streaming algorithms, which are the focus of this part of the thesis. Interestingly, each of these areas imposes additional requirements on the classical model of communication complexity: in interactive coding, we study communication complexity under noise; in auction design, we study communication complexity with incentives; and in multi-pass streaming, we consider communication complexity with few rounds of communication. While these three topics are seemingly very different, they all have strong connections with communication complexity, and studying them together often leads to deep insights.

1 0

Divyarthi Mohan will present her FPO "Simplicity and Optimality in Algorithmic Economics: Multi-Item Auctions and Social Learning" on Wednesday, July 14, 2021 at 2:30PM via Zoom.
by jfarquer＠cs.princeton.edu 07 Jul '21

07 Jul '21

Divyarthi Mohan will present her FPO "Simplicity and Optimality in Algorithmic Economics: Multi-Item Auctions and Social Learning" on Wednesday, July 14, 2021 at 2:30PM via Zoom. Zoom Link: https://princeton.zoom.us/j/94629442885?pwd=SURmMDBwYlg3YUp5YVVCMENvMEUrZz09 The members of Divya’s committee are as follows: Matt Weinberg ( Adviser), Readers: Mark Braverman, Nicole Immorlica (Microsoft Research); Examiners: Bernard Chazelle, Ran Raz, Matt Weinberg A copy of her thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend her talk. Abstract follows below: Typically, algorithms are designed to find the best possible solution for a given input, while efficiently using resources. But in many settings, algorithms face an additional challenge: inputs are provided by strategic agents who may have different objectives than those of the algorithm designer. As a result, the field of algorithmic game theory emerged to understand and design algorithms in the presence of strategic agents. This thesis makes progress towards understanding simplicity in algorithmic game theory and when simplicity results in good outcomes; we focus on two main sub areas of algorithmic economics: multi-item auction theory and social learning. We consider the problem of revenue maximization when selling 𝑛 items to a single unit-demand buyer. Unfortunately, optimal auctions for selling multiple items can be un[1]reasonably complex and computationally intractable. Our work shows that simple mechanisms can achieve almost optimal revenue. We approach the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result is a mechanism that gets a (1 − 𝜀)-approximation to the optimal revenue in time quasi-polynomial in 𝑛. We also study how information aggregates in networks through simple majority dynamics. We consider a model where agents make binary decisions, and each agent gets a private signal denoting which decision is better. Our main result proves that when the network is a tree formed according to the preferential attachment model, with high probability, the process stabilizes in a correct majority. Finally, we study a model of social learning between two Bayesian agents (a sender and a receiver) with limited/structured communication. In our model, to reflect real social exchanges, agents simply share a signal (or anecdote) they observed instead of sending arbitrary messages. A key result in our work shows that, when the agents have a fundamental difference, the optimal communication scheme can vary drastically (from sending the most representative anecdote to an extremely biased anecdote) depending on whether the receiver can observe the communication scheme used by the sender.

1 0