April 2011 - talks - lists.cs.princeton.edu

DH Lee General exam
by Melissa Lawson 29 Apr '11

29 Apr '11

Donghun Lee will present his research seminar/general exam on Wednesday May 4 at 1PM in Room 402. The members of his committee are: Warren Powell (ORFE, advisor), Rob Schapire, and Tom Funkhouser. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------- Abstract Value iteration and Q learning algorithms overestimate their value functions due to bias introduced by the maximum operator in the update rules. The bias can be substantial when these algorithms are applied to problems which contain large variances in rewards due to innate stochasticity in the cost function. This problem gets worse as the action space gets larger. We aim to bound the value function when there exist such bias introduced by the maximum operator in these algorithms. We seek to gain insights into the rate of convergence of the value function in the presence of high levels of noise in the cost function. Reading List Books . Powell,W. B. (2007). Approximate Dynamic Programming: Solving the Curses of Dimensionality, chapter 6, pages 179-224. Wiley-Interscience . Bertsekas, D. P. (2009). Dynamic Programming and Optimal Control, chapter 6 sections 6.1-6.5, pages 327-446. Athena Scientific . Russell, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach, 2nd Edition, chapter 21, pages 763-789. Prentice Hall Papers . Even-Dar, E. and Mansour, Y. (2003). Learning rates for Q-learning. Journal of Machine Learning Research, 5:1-25. . Kearns, M. and Singh, S. (1999). Finite-sample convergence rates for Q-learning and indirect algorithms. In Neural Information Processing Systems, volume 12, pages 996-1002. MIT Press. . Kulkarni, S. R. and Horn, C. S. (1996). An alternative proof for convergence of stochastic approximation algorithms. IEEE Transactions on Automatic Control, 41(3):419-424. . Lim, S. H. and DeJong, G. (2005). Towards finite-sample convergence of direct reinforcement learning. In Proceedings of European Conference on Machine Learning, pages 230-241. . Strehl, A. L., Li, L., and Littman, M. L. (2009). Reinforcement learning in finite MDPs: PAC analysis. Journal of Machine Learning Research, 10:2413-2444. . Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:185-202. . Wang, I.-J., Chong, E. K., and Kulkarni, S. R. (1996). Equivalent necessary and sufficient conditions on noise sequences for stochastic approximation algorithms. Advances in Applied Probability, 28:1996.

1 1

C Schlesinger general exam
by Melissa Lawson 28 Apr '11

28 Apr '11

Cole Schlesinger will present his research seminar/general exam on Wednesday May 4 at 10AM in Room 402. The members of his committee are: David Walker (advisor), David August, and Andrew Appel. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------------------- Abstract: Modern applications contain libraries and components written by different people at different times in different languages, often including unsafe languages like C or C++. As a result, one bug, such as a buffer overflow, in any component, can compromise the security and reliability of every other component. To help mitigate these problems, we introduce Yarra, a conservative extension to C with mechanisms for enforcing data integrity and partial safety, even when code is linked against unknown C libraries or binaries. Yarra programmers specify their data integrity requirements by declaring critical data types and ascribing these critical types to important data structures. Yarra guarantees that such critical data is only written through pointers with the given static type. Any attempt to write to critical data through a pointer with an invalid type (perhaps because of a buffer overrun) is detected dynamically. We formalize Yarra's semantics and prove the soundness of a program logic designed for use with the language. A key contribution is to show that Yarra's semantics are strong enough to support sound local reasoning and the use of a frame rule, even across calls to unknown, unverified code. We evaluate a prototype implementation of a compiler and runtime system for Yarra by using it to harden four common server applications against known non-control data vulnerabilities. We show that Yarra defends against these attacks with only a negligible impact on their end-to-end performance. Reading list: Textbooks: - Pierce, Benjamin. Types and Programming Languages. - Winskel, Glynn. The Formal Semantics of Programming Langauges. (Chapters 1 - 6). Formal methods papers: - S. Ishtiaq, P. O'Hearn. BI as an Assertion Language for Mutable Data Structures. In POPL, 2001. - P. O'Hearn, H. Yang, J. Reynolds. Separation and Information Hiding. In POPL, 2004. - S. K. Lahiri, S. Qadeer, D. Walker. Linear Maps. In PLPV, 2011. - G. Tan. JNI Light: An Operational Model for the Core JNI. In APLAS, 2010. - G. C. Necula, S. McPeak, and W. Weimer. CCured: Type-Safe Retrofitting of Legacy Code. In POPL, 2002. Systems papers: - S. Chen, J. Xu, E. C. Sezer, P. Gauriar, and R. K. Iyer. Noncontrol-data attacks are realistic threats. In Usenix Security (SSYM), 2005. - R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in C programs. In AADEBUG, 1997. - S. Nagarakatte, J. Zhao, M. M. K. Martin, and S. Zdancewic. SoftBound: Highly compatible and complete spatial memory safety for C. In PLDI, 2009. - E. D. Berger, T. Yang, and G. Novark. Grace: Safe multithreaded programming for C/C++. In OOPSLA, 2009. - R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham. Efficient software-based fault isolation. In SOSP, pages 203 - 216, 1993.

1 0

P Gopalan general exam
by Melissa Lawson 27 Apr '11

27 Apr '11

Prem Gopalan will present his research seminar/general exam on Wednesday May 4 at 9:30 AM in Room 302. The members of his committee are: Mike Freedman (advisor), Jen Rexford, and Margaret Martonosi. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. -------------------------------- Abstract Historically, Internet services provided clients with access to the resources of a particular host. However, today's services are no longer defined by a single host or confined to a fixed location. Yet, the network architecture continues to impose a coupling between hosts and services by binding connections to topology-dependent addresses, rather than topology-independent service names -- complicating everything from server replication, load balancing, and virtual-machine migration, to client mobility and multi-homing. We propose a new service access layer that redefines the interaction between the network and transport layers. This layer provides the "thin waist" needed to enable direct communication on service names, decouple service connections from network identifiers, and enhance the network's awareness of service availability. In this talk, we focus on how to rearchitect today's end-host network stack to include the service access layer while maintaining backwards compatibility with today's IP networks and requiring minimal changes to applications. We present the design of transport protocols running in this framework, and evaluate our Linux implementation. Reading list Books Andrew S. Tanenbaum. Computer Networks. Prentice Hall; 4th edition. Papers [1] H. Balakrishnan, K. Lakshminarayanan, S. Ratnasamy, S. Shenker, I. Stoica, and M. Walfish. A layered naming architecture for the internet. In ACM SIGCOMM '04, pages 343-352, New York, NY, USA, 2004. [2] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica. A data-oriented (and beyond) network architecture. In ACM SIGCOMM '07, pages 181-192, New York, NY, USA, 2007. [3] E. Kohler, M. Handley, and S. Floyd. Designing DCCP: congestion control without reliability. In SIGCOMM '06, pages 27-38, New York, NY, USA, 2006. [4] Gregory R. Ganger, Dawson R. Engler, M. Frans Kaashoek, Hector M. Briceno, Russell Hunt, and Thomas Pinckney. Fast and flexible Application-Level Networking on Exokernel Systems. In ACM Transactions on Computer Systems 20(1), February 2002, pages 49-83. [5] Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. The Click modular router. ACM Transactions on Computer Systems 18(3), August 2000, pages 263-297. [6] Raiciu, Costin and Pluntke, Christopher and Barre, Sebastien and Greenhalgh, Adam and Wischik, Damon and Handley, Mark. Data center networking with multipath TCP. In Hotnets '10: Proceedings of the Ninth ACM SIGCOMM Workshop on Hot Topics in Networks, pages 10:1-10:6, 2010. [7] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. Vl2: a scalable and flexible data center network. In SIGCOMM '09, pages 51-62, New York, NY, USA, 2009. [8] R. Niranjan Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, and A. Vahdat. Portland: a scalable fault-tolerant layer 2 data center network fabric. In SIGCOMM '09, pages 39-50, New York, NY, USA, 2009. ACM. [9] A.C. Snoeren, H.Balakrishnan. An End-to-End Approach to Host Mobility. In MobiCom, 2000. [10] B. Ford, J. Iyengar. Breaking Up the Transport Logjam, Bryan Ford and Janardhan Iyengar. In HotNets, 2008.

1 0

Nadia Heninger FPO
by Melissa Lawson 26 Apr '11

26 Apr '11

Nadia Heninger will present her FPO on Tuesday May 3 at 2PM in Room 402. The members of her committee are: Bernard Chazelle, advisor; Ed Felten and Henry Cohn (MSR New England), readers; Boaz Barak and Moses Charikar, nonreaders. A copy of her thesis, "Error Correction and the Cryptographic Key", is on display in Room 310. Everyone is invited to attend her talk.

1 0

Connelly Barnes FPO
by Melissa Lawson 26 Apr '11

26 Apr '11

Connelly Barnes will present his FPO on Tuesday May 3 at 12:30PM in Room 402. The members of his committee are; Adam Finkelstein, advisor; Szymon Rusinkiewicz and Dan Goldman (Adobe), readers; Tom Funkhouser and Bob Sedgewick, nonreaders. A copy of his thesis, "PatchMatch: A Fast Randomized Matching Algorithm with Application to Image and Video", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Corey Toler-Franklin FPO
by Melissa Lawson 26 Apr '11

26 Apr '11

Corey Toler-Franklin will present her FPO on Tuesday May 3 at 10AM in Room 402. The members of her committee are: Szymon Rusinkiewicz, advisor; Tom Funkhouser and Holly Rushmeier (Yale), readers; Adam Finkelstein and David Blei, nonreaders. A copy of her thesis, "Matching, Archiving and Visualizing Cultural Heritage Artifacts Using Multi-Channel Images", is on display in Room 310. Everyone is invited to attend her talk.

1 0

R Harrison MSE thesis talk
by Melissa Lawson 25 Apr '11

25 Apr '11

Rob Harrison will present his MSE thesis talk on Friday April 29 at 10AM in Room 402. Jen Rexford is his advisor, and David Walker is his reader. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------- ABSTRACT: Network administrators must configure network devices to simultaneously provide several interrelated services such as routing, load balancing, traffic monitoring, and access control. Unfortunately, most interfaces for programming networks are defined at the low level of abstraction supported by the underlying hardware, leading to complicated programs with subtle bugs. We present Frenetic, a high-level language for programming networks that enables writing programs in a declarative and compositional style, with a simple ``program like you see every packet'' abstraction. Frenetic consists of a rich network query language, a network management library, and a run-time system. The run-time system efficiently manages the low-level details of installing, uninstalling, and querying the low-level packet-processing rules on physical switches. We describe the design of the Frenetic language and run-time system, an implementation on top of the OpenFlow architecture, experiments and example programs that validate our design choices.

1 0

Chris Bregler Talk on Monday at noon in CS 402
by Thomas Funkhouser 25 Apr '11

25 Apr '11

**There will be a talk of broad interest by Chris Bregler from NYU in the PIXL lunch talk series at noon on Monday in CS 402. All are welcome. ** // *From Eye-Balls to Ball-Games: Next-Gen Motion Capture for Science and Entertainment* /Chris Bregler, NYU / *Abstract* This talk will cover several research projects centered around the use of vision and motion capture for animation, recognition, and gaming. This includes human movements as diverse as subtle eye-blinks, lip-motions, spine-deformations, human walks and dances, politicians, base-ball pitchers, and the production of the largest motion capture game to date. The technical content of the talk focuses on the trade-off between data-driven models of human motion vs. analytically derived and perceptually driven models using dancers, animators, linguists, and other domain experts. This is demonstrated by sub-pixel tracking in Hollywood productions, reading the body-language of public figures, visualizing the pitches of NY Yankees Mariano Rivera, and the making of crowd mocap games in various cultures. ------------------------------------------------------------------------

1 1

C Beck general exam
by Melissa Lawson 20 Apr '11

20 Apr '11

Chris Beck will present his research seminar/general exam on Monday April 25 at 11AM in room 401 (note room). The members of his committee are: Sanjeev Arora (advisor), Bernard Chazelle, and Moses Charikar. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------------------- Abstract: For modern SAT solvers based on DPLL with clause learning, the two major bottlenecks are the time and memory used by the algorithm. There is a well known correspondence between these algorithms and the Resolution proof system, in which these resources correspond to the length and space of proofs. Lately there has been great theoretical interest in understanding the interplay of these two resources, and in obtaining Time Space Tradeoff results. In 2010, Eli Ben-Sasson and Jakob Nordström demonstrated formulae which have linear sized proofs using linear space, but which require exponentially large proofs when the space is constrained to be n / log n. It remains a major open question to obtain similar lower bounds against time but with a more mild space assumption, since in practice SAT solvers generally are not used on instances so large that they exceed the available memory. We obtain strong tradeoff results for Regular Resolution, a restricted form of General Resolution. For each k, we can find formulae of length n which may be proved in time n^(k+1) with space n^k, but such that with space at most n^(k - epsilon), superpolynomial time is necessary in any proof. Our analysis relies on a random adversary related to those used in Prover Adversary games, normally thought to be relevant only to very weak proof systems. This innovation permits a comparatively simple lower bound argument, avoiding completely the use of random restrictions. Reading List: Resolution (1): Eli Ben-Sasson, Avi Wigderson <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/w/Wigderson:Avi…> : Short proofs are narrow - resolution made simple. J. ACM 48 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jacm/jacm48.html#Ben-…> (2): 149-169 (2001) Resolution Space (3): Michael Alekhnovich <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/a/Alekhnovich:M…> , Eli Ben-Sasson, Alexander A. Razborov <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/r/Razborov:Alex…> , Avi Wigderson <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/w/Wigderson:Avi…> : Space Complexity in Propositional Calculus. SIAM J. Comput. 31 <http://www.informatik.uni-trier.de/%7Eley/db/journals/siamcomp/siamcomp31.h… hBRW02> (4): 1184-1211 (2002) Albert Atserias, Víctor Dalmau <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/d/Dalmau:V=iacu…> : A combinatorial characterization of resolution width. J. Comput. Syst. Sci. 74 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jcss/jcss74.html#Atse…> (3): 323-334 (2008) Eli Ben-Sasson, Jakob Nordström <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/n/Nordstr=ouml=…> : Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs. Electronic Colloquium on Computational Complexity (ECCC) 16 <http://www.informatik.uni-trier.de/%7Eley/db/journals/eccc/eccc16.html#Ben-…> : 34 (2009) Polynomial Calculus (4): <http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-SassonI99.xml> Image removed by sender. bibliographical record in XMLEli Ben-Sasson, Russell Impagliazzo <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/i/Impagliazzo:R…> : Random CNF's are Hard for the Polynomial Calculus. FOCS 1999 <http://www.informatik.uni-trier.de/%7Eley/db/conf/focs/focs99.html#Ben-Sass…> : 415-421 Samuel R. Buss <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/b/Buss:Samuel_R…> , Dima Grigoriev <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/g/Grigoriev:Dim…> , Russell Impagliazzo, Toniann Pitassi <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/p/Pitassi:Tonia…> : Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62 <http://www.informatik.uni-trier.de/%7Eley/db/journals/jcss/jcss62.html#Buss…> (2): 267-289 (2001) Russell Impagliazzo, Pavel Pudlák <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/p/Pudl=aacute=k…> , Jiri Sgall <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/s/Sgall:Jiri.ht…> : Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Computational Complexity 8 <http://www.informatik.uni-trier.de/%7Eley/db/journals/cc/cc8.html#Impagliaz…> (2): 127-144 (1999) Matthew Clegg <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/c/Clegg:Matthew…> , Jeff Edmonds <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/e/Edmonds:Jeff.…> , Russell Impagliazzo: Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. STOC 1996 <http://www.informatik.uni-trier.de/%7Eley/db/conf/stoc/stoc1996.html#CleggE…> : 174-183 AC^0-Frege (2): Paul Beame and Søren Riis. More on the relative strength of counting principles <http://www.cs.washington.edu/homes/beame/papers/riis.ps> . In Paul W. Beame and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 13-35. American Mathematical Society, 1998. Also related: Paul Beame. A switching lemma primer <http://www.cs.washington.edu/homes/beame/papers/primer.ps> . Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, November 1994. SAT solvers & Model Checking (1): Lintao Zhang, Conor F. Madigan, Matthew H. Moskewicz, Sharad Malik, "Efficient Conflict Driven Learning in a Boolean Satisfiability Solver," iccad, pp.279, 2001 International Conference on Computer-Aided Design (ICCAD '01), 2001 Verification/Model Checking(1): <http://scholar.google.com/scholar?q=%22Bounded+Model+Checking+Using+Satisfi… g.%22> Image removed by sender. Google scholar <http://dblp.uni-trier.de/rec/bibtex/journals/fmsd/ClarkeBRZ01> Image removed by sender. BibTeX <http://dblp.uni-trier.de/rec/bibtex/journals/fmsd/ClarkeBRZ01.xml> Image removed by sender. bibliographical record in XMLEdmund M. Clarke <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/c/Clarke:Edmund…> , Armin Biere, Richard Raimi <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/r/Raimi:Richard…> , Yunshan Zhu <http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/z/Zhu:Yunshan.h…> : Bounded Model Checking Using Satisfiability Solving. Formal Methods in System Design 19 <http://www.informatik.uni-trier.de/%7Eley/db/journals/fmsd/fmsd19.html#Clar…> (1): 7-34 (2001)

1 0

R Wang MSE thesis talk
by Melissa Lawson 19 Apr '11

19 Apr '11

Richard Wang will present his master's thesis talk on Friday April 22 at 10:30AM in Room 301. His advisor is Jen Rexford. Everyone is invited to attend his talk. His abstract follows below. -------------------- abstract: Today's data centers host online services on multiple servers, with a front-end load balancer directing each client request to a particular replica. Dedicated load balancers are expensive and quickly become a single point of failure and congestion. The OpenFlow standard enables an alternative approach where the commodity network switches divide traffic over the server replicas, based on packet-handling rules installed by a separate controller. However, the simple approach of installing a separate rule for each client connection (or "microflow") leads to a huge number of rules in the switches and a heavy load on the controller. We argue that the controller should exploit switch support for wildcard rules for a more scalable solution that directs large aggregates of client traffic to server replicas. We present algorithms that compute concise wildcard rules that achieve a target distribution of the traffic, and automatically adjust to changes in load-balancing policies without disrupting existing connections. We implement these algorithms on top of the NOX OpenFlow controller, evaluate their effectiveness, and propose several avenues for further research.

1 0