- talks - lists.cs.princeton.edu

colloquium speaker Zachary Kincaid Wed, March 25, 12:30pm
by Nicole E. Wagenblast 24 Mar '15

24 Mar '15

Colloquium Speaker Zachary Kincaid, University of Toronto Wednesday, March 25, 12:30pm Computer Science 105 Parallel Proofs for Parallel Programs Today's software systems are large and complex - beyond the scope of comprehension of any one person. My research is motivated by the question of how machines can help humans better understand their code and aid the construction of reliable, secure, and efficient systems. Multi-threading is a long-standing obstacle to reasoning by both humans and machines. Conventionally, this obstacle is met by developing clever ways to reason about the program as if it were executing sequentially. In this talk, I will argue that we should embrace parallelism, not hide from it. I will discuss new *fundamentally parallel* foundations for automated program analysis, which allow the parallelism present in a program to be explicitly maintained and enable tractable automated reasoning and succinct proofs. In other words: my talk will be on parallel proofs for parallel programs. Zachary Kincaid is a PhD candidate in the Department of Computer Science at the University of Toronto. He is interested in developing automated reasoning techniques to facilitate the construction of high-performance, dependable software. Zak's research focuses on static analysis and program verification, with a particular emphasis on multi-threaded programs. He has also made contributions to theorem proving and program synthesis.

1 0

Colloquium Speaker Aaron Sidford, Today, 4:30pm
by Nicole E. Wagenblast 23 Mar '15

23 Mar '15

Colloquium Speaker Aaron Sidford, Massachusetts Institute of Technology Monday, March 23, 4:30pm Computer Science Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier Over the past decade there has been a revolution in the field of algorithmic graph theory. Using techniques from disparate areas of computer science, ranging from numerical analysis, to data structures, to continuous optimization, there have been numerous breakthroughs in improving the running time for solving classic problems in combinatorial optimization. In this talk I will discuss my work in this area and show how it has led to both improved running times for solving fundamental problems in combinatorial optimization and the creation of improved iterative methods for solving classic continuous optimization problems. After briefly discussing this high-level research program, I will provide a more detailed illustration through my recent work on linear programming and the maximum flow problem. In particular, I will present a new algorithm for solving linear programs that improves upon the convergence rate of previous state-of-the-art methods. Where the convergence rate of the previous efficient methods depended on the larger of the number of variables and the number of constraints ours depends on the smaller. Our algorithm approximately matches the convergence rate of the "universal barrier" of Nesterov and Nemirovskii while greatly decreasing the iteration costs. Furthermore, I will discuss how our method outperforms the universal barrier in particular cases, yielding the fastest known running times for solving dense instances of the directed maximum flow problem) and more generally, minimum cost flow. This talk will assume no previous experience with linear programming algorithms, convex optimization, or graph theory. Aaron Sidford is a PhD student in the electrical engineering and computer science department at the Massachusetts Institute of Technology, advised by Jonathan Kelner. His research interests lie broadly in the theory of computation and the design of efficient algorithms. He is particularly interested in problems at the intersection of combinatorial optimization and numerical analysis. Since he began his PhD in 2011, his research has focused on improving the running time for solving classic problems in algorithmic graph theory while using and improving tools ranging from convex analysis to data structures to spectral graph theory.

1 0

Colloquium Speaker Aaron Sidford, Mon, March 23, 4:30pm
by Nicole E. Wagenblast 22 Mar '15

22 Mar '15

Colloquium Speaker Aaron Sidford, Massachusetts Institute of Technology Monday, March 23, 4:30pm Computer Science Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier Over the past decade there has been a revolution in the field of algorithmic graph theory. Using techniques from disparate areas of computer science, ranging from numerical analysis, to data structures, to continuous optimization, there have been numerous breakthroughs in improving the running time for solving classic problems in combinatorial optimization. In this talk I will discuss my work in this area and show how it has led to both improved running times for solving fundamental problems in combinatorial optimization and the creation of improved iterative methods for solving classic continuous optimization problems. After briefly discussing this high-level research program, I will provide a more detailed illustration through my recent work on linear programming and the maximum flow problem. In particular, I will present a new algorithm for solving linear programs that improves upon the convergence rate of previous state-of-the-art methods. Where the convergence rate of the previous efficient methods depended on the larger of the number of variables and the number of constraints ours depends on the smaller. Our algorithm approximately matches the convergence rate of the "universal barrier" of Nesterov and Nemirovskii while greatly decreasing the iteration costs. Furthermore, I will discuss how our method outperforms the universal barrier in particular cases, yielding the fastest known running times for solving dense instances of the directed maximum flow problem) and more generally, minimum cost flow. This talk will assume no previous experience with linear programming algorithms, convex optimization, or graph theory. Aaron Sidford is a PhD student in the electrical engineering and computer science department at the Massachusetts Institute of Technology, advised by Jonathan Kelner. His research interests lie broadly in the theory of computation and the design of efficient algorithms. He is particularly interested in problems at the intersection of combinatorial optimization and numerical analysis. Since he began his PhD in 2011, his research has focused on improving the running time for solving classic problems in algorithmic graph theory while using and improving tools ranging from convex analysis to data structures to spectral graph theory.

1 0

colloquium speaker Zachary Kincaid Wed, March 25, 12:30pm
by Nicole E. Wagenblast 19 Mar '15

19 Mar '15

Colloquium Speaker Zachary Kincaid, University of Toronto Wednesday, March 25, 12:30pm Computer Science 105 Parallel Proofs for Parallel Programs Today's software systems are large and complex - beyond the scope of comprehension of any one person. My research is motivated by the question of how machines can help humans better understand their code and aid the construction of reliable, secure, and efficient systems. Multi-threading is a long-standing obstacle to reasoning by both humans and machines. Conventionally, this obstacle is met by developing clever ways to reason about the program as if it were executing sequentially. In this talk, I will argue that we should embrace parallelism, not hide from it. I will discuss new *fundamentally parallel* foundations for automated program analysis, which allow the parallelism present in a program to be explicitly maintained and enable tractable automated reasoning and succinct proofs. In other words: my talk will be on parallel proofs for parallel programs. Zachary Kincaid is a PhD candidate in the Department of Computer Science at the University of Toronto. He is interested in developing automated reasoning techniques to facilitate the construction of high-performance, dependable software. Zak's research focuses on static analysis and program verification, with a particular emphasis on multi-threaded programs. He has also made contributions to theorem proving and program synthesis.

1 0

Colloquium Speaker Aaron Sidford, Mon, March 23, 4:30pm
by Nicole E. Wagenblast 17 Mar '15

17 Mar '15

Colloquium Speaker Aaron Sidford, Massachusetts Institute of Technology Monday, March 23, 4:30pm Computer Science Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier Over the past decade there has been a revolution in the field of algorithmic graph theory. Using techniques from disparate areas of computer science, ranging from numerical analysis, to data structures, to continuous optimization, there have been numerous breakthroughs in improving the running time for solving classic problems in combinatorial optimization. In this talk I will discuss my work in this area and show how it has led to both improved running times for solving fundamental problems in combinatorial optimization and the creation of improved iterative methods for solving classic continuous optimization problems. After briefly discussing this high-level research program, I will provide a more detailed illustration through my recent work on linear programming and the maximum flow problem. In particular, I will present a new algorithm for solving linear programs that improves upon the convergence rate of previous state-of-the-art methods. Where the convergence rate of the previous efficient methods depended on the larger of the number of variables and the number of constraints ours depends on the smaller. Our algorithm approximately matches the convergence rate of the "universal barrier" of Nesterov and Nemirovskii while greatly decreasing the iteration costs. Furthermore, I will discuss how our method outperforms the universal barrier in particular cases, yielding the fastest known running times for solving dense instances of the directed maximum flow problem) and more generally, minimum cost flow. This talk will assume no previous experience with linear programming algorithms, convex optimization, or graph theory. Aaron Sidford is a PhD student in the electrical engineering and computer science department at the Massachusetts Institute of Technology, advised by Jonathan Kelner. His research interests lie broadly in the theory of computation and the design of efficient algorithms. He is particularly interested in problems at the intersection of combinatorial optimization and numerical analysis. Since he began his PhD in 2011, his research has focused on improving the running time for solving classic problems in algorithmic graph theory while using and improving tools ranging from convex analysis to data structures to spectral graph theory.

1 0

Fwd: EE Seminar - Somayeh Sojoudi - March 23rd
by Jennifer Rexford 13 Mar '15

13 Mar '15

> > > > Speaker: > Somayeh Sojoudi > Title: > Computational Methods for Complex Systems: From Brain to Power Networks > Day: > Monday, March 23, 2015 > > > Time: > 4:30 pm > Room: > B205, E-Quad > Host: > Prof. Naveen Verma > > > > > > > > > Abstract: > In this talk, we develop mathematical techniques for the analysis, modeling and control of complex networks such as brain and electrical power networks. Two main questions to be addressed are as follows: 1) how to learn a model from data? 2) how to deal with the nonlinearity of a system? Our results will be presented in the contexts of brain and power systems separately. > > Brain networks: The study of brain networks enables us to address fundamental problems ranging from understanding how the brain processes speech to localizing seizure-generating areas in epilepsy patients. In this talk, we explore three types of brain networks, namely structural, functional, and effective connectivity. We offer mathematical results and empirical observations through three case studies. First, we analyze brain networks under various speech conditions using ECoG technology. Second, we discuss the communication networks in the hippocampus and entorhinal cortex. Third, we study the modeling and analysis of the brain functional connectivity using functional MRI technology. > > Power networks: The real-time operation of a power network depends on a nonlinear optimization problem, named optimal power flow (OPF), which is solved every 5-15 minutes in practice. According to recent Federal Energy Regulatory Commission's studies, 5% improvement in the solution of OPF reduces the annual cost by more than one billion dollars. In this talk, we propose a convexification technique for the long-standing OPF problem, followed by theoretical results and simulations on real data. > > > Bio: > Somayeh Sojoudi is currently an assistant research scientist at the New York University (NYU) School of Medicine, where she collaborates with a team of neuroscientists, neurologists and neurosurgeons at the comprehensive epilepsy center and the neuroscience institute. Her current research is focused on the study of the brain and the development of efficient mathematical tools and techniques for neuroscience and clinical neurology applications. Before joining NYU, she was a PhD student in Control and Dynamical Systems at the California Institute of Technology. Her interdisciplinary research on complex systems span control systems, optimization theory, power systems, communication networks, and health. She is a co-author of a best student paper award finalist for the 53rd IEEE Conference on Decision and Control 2014. She is recipient of a postgraduate scholarship from the Natural Sciences and Engineering Research Council of Canada and had been awarded the 2008 F. A. Gerard Prize. > > > > > Heather Evans > Assistant to the Chair > Department of Electrical Engineering > Princeton University > Engineering Quadrangle, B-210 > Olden Street > Princeton, NJ 08544 > (p): 609-258-7282 > (f): 609-258-0119 > heathere(a)princeton.edu > > >

1 0

Colloquium Speaker Nati Srebro, Thrusday March 12, 4:30pm
by Nicole E. Wagenblast 12 Mar '15

12 Mar '15

CSML/CS Colloquium Speaker Nati Srebro Thursday, March 12, 4:30pm Computer Science 105 The Power of Asymmetry in Binary Hashing When looking for similar objects, like images and documents, and especially when querying a large remote data-base for similar objects, it is often useful to construct short similarity-preserving binary hashes. That is, to map each image or document to a short bit strings such that similar objects have similar bit strings. Such a mapping lies at the root of nearest neighbor search methods such as Locality Sensitive Hashing (LSH) and is recently gaining popularity in a variety of vision, image retrieval and document retrieval applications. In this talk I will demonstrate, both theoretically and empirically, that even for symmetric and well behaved similarity measures, much could be gained by using two different hash functions---one for hashing objects in the database and an entirely different hash function for the queries. Such asymmetric hashings can allow to significantly shorter bit strings and more accurate retrieval. Joint work with Behnam Neyshabur, Yury Makarychev and Russ Salakhutdinov

1 1

Colloquium Speaker Daniel Abadi Thurs march 12, 12:30pm
by Nicole E. Wagenblast 12 Mar '15

12 Mar '15

Colloquium Speaker Daniel Abadi , Yale University Thursday, March 12, 12:30pm Computer Science 105 Deterministic Transaction Processing The database system was one of the first highly concurrent systems ever designed, and has served as a blueprint for the design of many subsequent concurrent computing systems. The decision to allow the system to process concurrent transactions nondeterministically has led to countless headaches from bugs (and debugging), security, replication, and general code complexity. In this talk, we will discuss a fundamentally different design for concurrent execution of transactions in database systems that guarantees that the final state of the database is deterministically prescribed from the input to the system. We look at the consequences of the deterministic design, from throughput and latency, to replication and recovery. We will also discuss a radically different mechanism for processing transactions that is enabled by the deterministic execution framework: lazy transactional processing. Instead of immediately processing transactions as they enter the system, transactions are only partially processed, with the remainder of processing performed at an optimal time for the database system. We will discuss the cache locality, load balancing, and performance benefits of our lazy processing framework. Daniel Abadi is a member of the computer science faculty at Yale University where he performs research on database system architecture and implementation, especially at the intersection with scalable and distributed systems. He is known for the development of the storage and query execution engines of the C-Store (column-oriented database) prototype, which was commercialized by Vertica and eventually acquired by Hewlett-Packard. More recently, his HaodopDB research on fault tolerant scalable analytical database systems was commercialized by Hadapt and acquired last summer by Teradata. Abadi has been a recipient of a Churchill Scholarship, an NSF CAREER Award, a Sloan Research Fellowship, the VLDB Early Career Researcher Award, the SIGMOD Jim Gray Doctoral Dissertation Award, and a VLDB best paper award.

1 2

Omri Weinstein will present his FPO March 13, 2015 at 1pm in CS Room 301
by Nicki Gotsis 10 Mar '15

10 Mar '15

Omri Weinstein will present his FPO on March 13, 2015 at 1pm in CS Room 301. The members of his committee are: Mark Braverman, advisor; Anup Rao(University of Washington), reader; Zeev Dvir, reader; Sanjeev Arora, non-reader; Michael Saks(Rutgers), non-reader. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Interactive Information Complexity and Applications Abstract: ======= Few models in the history of theoretical computer science have affected the field in so many ways as profoundly as communication complexity. With applications in nearly every area of computer science, this model constitutes one of the few known techniques for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is therefore a promising approach for making progress in other computational models such as streaming, property testing, distributed computing, circuit complexity and data structures. One striking example of such tool is information theory, introduced by Shannon in the late 1940's in the context of the one way data transmission problem. Shannon's work revealed the intimate connection between information and communication, namely, that the amortized transmission cost of a random message is equal to the amount of information it contains. Classical information theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation in order to accomplish a desirable task. The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in interactive setups, such as the communication complexity model. Our main measure if interest is the Information Complexity of a function, which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the underlying task. We demonstrate the broad power of this theory via applications to communication complexity, data streaming, circuit lower bounds, privacy and economics. In particular, I will discuss how information complexity helped us make progress on some of the most fundamental questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture.

1 0

Friday March 6: 1:30-2:30 talk on Networks of Networks of Quantum Repeaters
by Margaret Martonosi 05 Mar '15

05 Mar '15

Reminder: Talk tomorrow afternoon! Speaker: Rodney Van Meter, Keio University Title: Networks of Networks of Quantum Repeaters Date/time: Friday March 6, 1:30-2:30pm. Location: CS 401. Abstract: Experimental progress toward quantum repeaters is moving at a tremendous rate, and theorists have proposed half a dozen approaches to managing errors to create high-fidelity entanglement along a chain of repeaters. The next frontier is extending from one-dimensional chains to complex topologies. Problems in network engineering include robust protocol design and resource management. I will give an overview of these issues, then discuss the even more daunting challenge of creating networks of networks -- a true quantum Internet -- capable of coupling networks that are heterogeneous in both physical technology and error management scheme. Bio: Rodney Van Meter received a B.S. in engineering and applied science from the California Institute of Technology in 1986, an M.S. in computer engineering from the University of Southern California in 1991, and a Ph.D. in computer science from Keio University in 2006. His current research centers on quantum computer architecture and quantum networking. Other research interests include storage systems, networking, and post-Moore's Law computer architecture. He is now an Associate Professor of Environment and Information Studies at Keio University's Shonan Fujisawa Campus. Dr. Van Meter is a member of AAAS, ACM and IEEE. Host: Margaret Martonosi (contact me if you’d like to get on his one-on-one schedule.) Margaret Martonosi H. T. Adams '35 Professor of Computer Science. Princeton University ■ mrm(a)princeton.edu ■ http://www.princeton.edu/~mrm

1 0