- talks - lists.cs.princeton.edu

C Beck preFPO
by Melissa M. Lawson 28 Jan '14

28 Jan '14

Chris Beck will present his preFPO on Friday Jan 31 at 3PM in Room 402. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Lower Bounds for Time and Space In this thesis we study the computational limitations of restricted models of computation. We pay particular attention to ``simple'' algorithms for satisfiability, that is, algorithms which are permitted to use large amounts of traditional resources such as space and time, but whose correctness must be provable in a simple proof system. This has the consequence that when an algorithm accepts or rejects an input, the computation history corresponds to a simple propositional proof of the input's status, and that studying the structure of such proofs allows us to formally understand some of the difficulties faced by the algorithm. The fact that many algorithms yield proofs has been observed in a variety of scenarios in both theory and practice. Moreover, in many of these cases, proof complexity is the only known way to analyze the running time of such algorithms. >From a different point of view, our results are interesting because the techniques for proof lower bounds are closely related to the known techniques for circuit lower bounds. Lower bounds for circuits via random restrictions and via Razoborv's method of approximations are closely related to Haken's bottleneck counting method for Resolution lower bounds, and well-known work of Beame et al. shows that this analogy can be carried through even for AC0 Frege proofs. One of our most important contributions to the area is to show that the bottleneck counting technique can also be used to show time space trade-offs. Indeed, while previous time space tradeoffs used ad-hoc techniques and only applied in the sublinear space regime, we show that the same technique which gives (tight) proof size lower bounds can be vastly generalized to yield superpolynomial time space tradeoffs which are tight in the high space regime. It is an interesting question for future research whether our technique could also be used for restricted circuits, such as monotone circuits, or in a model such as read once algebraic branching programs. Our results are the following: - We give the first time space trade-off results for Resolution which are meaningful in the regime of {\emph{ superlinear}} space. More concretely, we give tautologies which have polynomial size resolution proofs which may be carried out in polynomial space (and which standard algorithms would find in polynomial time using polynomial memory), but for which even slightly reduced space entails a superpolynomial size resolution proof. This gives the first formal explanation for why DPLL+Clause Learning SAT solvers need a large amount of space to work well in practice, and gives evidence to support the main conjecture of Allender et al. (2012) regarding tree-width parameterized satisfiability. - We extend these techniques to the stronger Polynomial Calculus Resolution proof system, an algebraic system used sometimes in practice instead of traditional SAT solvers, based on Grobner Basis techniques. - We show that the Strong Exponential Time Hypothesis applies to the proof system of regular resolution, and thus to algorithms based on the original Davis Putnam procedure. We conjecture that SETH holds for general resolution, and improve the state of the art size lower bounds for resolution proofs. In particular, we show that Grover's black box search algorithm solves SAT faster than any classical SAT solver. - We expand upon recent work of Lovett and Viola, giving an explicit distribution of strings which is hard to approximately sample in AC0. Our results are essentially best possible in terms of the size of the circuits and quality of the approximation. In addition we prove a new concentration bound for collections of decision trees, and a structure theorem for these, which could be useful in future applications.

1 0

Tengyu Ma general exam - change of location!
by Melissa M. Lawson 20 Jan '14

20 Jan '14

Tengyu's general exam will now take place in the Sherrerd Hall conference room, Sherrerd 306, this Wednesday Jan 22 from 2-4PM. Sorry for any inconvenience. --Melissa

1 0

Tengyu Ma general exam
by Melissa M. Lawson 17 Jan '14

17 Jan '14

Tengyu Ma will present his research seminar/general exam on Wednesday January 22 at 2PM in Room 301 (note room!). The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and David Blei. 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. ----- Original Message ----- abstract I will mainly talk about our recent paper on deep learning provable bound for learning some deep representations. Deep learning, a modern variant of artificial neural net, has been a very powerful tool in recent years for many machine learning tasks such as image recognition, speech recognition and natural language processing. Variations of However, theoretically, it still remains mysterious why these modern heuristics and tricks together with millions of data result in big improvements in so many important questions. With the motivation to resolve these mysteries, this paper proposes a generative model for deep network, and provides an provable algorithm that can learn all the parameters and hidden variables unsupervisedly using polynomial time and polynomial samples generated from this network under some assumptions In more detail, the network we study has constant number of layers, each consecutive two layers are connected via a random sparse bipartite graph/matrix. The observed data at bottom are generated as follows: First a sparse hidden vector at the top layer is chosen, then the top layer activates some of the second layer nodes by multiplying the connection matrix and applying another point-wise threshold function, and then adding some small noise. Then the second layer activates the third using the same rules with the new connection matrix, so on and so forth. Our algorithms exploits the old Hebbian rule: "Things fire together wire together", that is, if two nodes in the same layer are correlated, then they are likely to connect to the same ancestor in the layer above them. This is the joint work with Sanjeev Arora, Aditya Bhaskara and Rong Ge. Reading list: 0. Algorithm Design, Jon Kleinberg, Éva Tardos 1. Ankur Moitra's lecture notes for the course Algorithmic Aspects of Machine Learning http://people.csail.mit.edu/moitra/996.html 2. Daniel Hsu's lecture notes for COMS 4772 Advanced Machine Learning (Fall 2013) http://www.cs.columbia.edu/~djhsu/4772/ 3. Machine Learning: A Probabilistic Perspective By Kevin P. Murphy (provided I could find it in library) http://mitpress.mit.edu/sites/default/files/titles/content/9780262018029_to… 4. Representation Learning: A Review and New Perspectives, by Yoshua Bengio, Aaron Courville, Pascal Vincent 5. Visualizing and Understanding Convolutional Networks http://arxiv.org/abs/1311.2901 6. ImageNet Classification with Deep Convolutional Neural Networks by Krizhevsky, A., Sutskever, I. and Hinton, G. E. 7. Generalized Denoising Auto-Encoders as Generative Models Bengio et al. http://arxiv.org/abs/1305.6663 8. On the Provable Convergence of Alternating Minimization for Matrix Completion 9. Tensor Decompositions for Learning Latent Variable Models by Anandkumar, Ge, Hsu, Kakade, Telgarsky 10. A. Kumar, R. Kannan, Clustering with Spectral Norm and the k-Means Algorithm 11. V. Chandrasekaran, P. Parrilo, A. Willsky, Latent Variable Graphical Model Selection via Convex Optimization

1 0

J Wetzel general exam
by Melissa M. Lawson 10 Jan '14

10 Jan '14

Joshua Wetzel will present his research seminar/general exam on Friday January 17 at 10AM in Room 302 (note room!). The members of his committee are: Mona Singh, advisor, Olga Troyanskaya, 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. ----- Original Message ----- Abstract: Protein-DNA interaction is a fundamental step in cellular regulation. Proteins known as transcription factors (TFs) are produced in order to either enhance or repress the expression of various gene products according to the particular needs of the cell at a given moment. They often do so by binding to the genome in specific locations according to the amino acid residues contained in their DNA-binding domain (DBD), which is the structural unit of the protein that is often used to classify TFs into groups. The largest class of TFs, comprising roughly half of the annotated TFs in eukaryotes, is defined by a DBD known as a Cys 2 His 2 zinc finger (C2H2-ZF). While the majority of DBDs can bind only a limited repertoire DNA sequences, members of the C2H2-ZF class span an extremely wide variety of DNA binding preferences. Moreover, these preferences appear to be determined largely by the identity of amino acids occupying only a few key positions of a structurally well-defined and semi-modular protein-DNA contact interface. However, the rules that govern DNA-binding preferences remain unclear, thwarting our ability to predict binding sites of endogenous C2H2-ZFs. Due to the large number of possible amino-acid combinations and the variety of DNA sequences they can potentially bind, high-throughput interaction screens and rigorous computational methods are necessary. In my talk, I’ll discuss the analysis of a high-throughput, randomized, synthetic screen of C2H2-ZF-DNA functional interactions obtained via the bacterial one-hybrid selection system. After extensive filtering, the data reveals hundreds to thousands of ‘canonical’ helices binding with varying levels of affinity to each of the 64 possible 3bp DNA targets, providing the most comprehensive view of C2H2-ZF-DNA interaction to date. I will explain an information theoretic analysis that validates an expanded view of the physical model for the C2H2-ZF-DNA binding interface and show methods for inferring DNA-binding profiles via integration of data from independent protein selections. Additionally, I extend the predictive scope of the data by adapting a classical nearest neighbors approach by leveraging information related to the physical binding model and frequently observed amino acid substitutions. I will demonstrate strong concordance between predicted binding profiles and their experimentally determined counterparts within the synthetic context, as well as generalizability of the data via prediction of binding profiles for naturally occurring C2H2-ZFs. Overall, the analysis reveals a complex binding landscape for C2H2-ZFs, which shows both agreement and conflict with previously proposed ‘codes’ of DNA-binding specificity. Reading List: 1. Jones, N. C. & Pevzner, P. A. An Introduction to Bioinformatics Algorithms . MIT Press (2004). (Textbook) 2. Stormo, G. D. & Zhao, Y. Determining the specificity of protein-DNA interactions. Nat. Rev. Genet. 11, 751–60 (2010). 3. Persikov, A. V. & Singh, M. An expanded binding model for Cys2His2 zinc-finger protein-DNA interfaces. Phys. Biol. 8 (3):035010 (2011). 4. Noyes, M. et al. A systematic characterization of factors that regulate Drosophila segmentation via a bacterial one-hybrid system. Nucleic Acids Res. 36 (8), 2547-60 (2008). 5. Klug, A. The discovery of zinc fingers and their applications in gene regulation and genome manipulation. Annu. Rev. Biochem. 79, 213–31 (2010). 6. Jolma, A. et al. DNA-binding specificities of human transcription factors. Cell 152, 327–39 (2013). 7. Benos, P. V., Lapedes, A. S. & Stormo, G. D. Probabilistic Code for DNA Recognition by Proteins of the EGR Family. J. Mol. Biol. 323, 701–727 (2002). 8. Enuameh, M. S. et al. Global analysis of Drosophila Cys ₂ -His ₂ zinc finger proteins reveals a multitude of novel recognition motifs and binding determinants. Genome Res. 23, 928–40 (2013). 9. Vaquerizas, J. M., Kummerfeld, S. K., Teichmann, S. a & Luscombe, N. M. A census of human transcription factors: function, expression and evolution. Nat. Rev. Genet. 10, 252–63 (2009). 10. Persikov, A. V & Singh, M. De novo prediction of DNA-binding specificities for Cys2His2 zinc finger proteins. Nucleic Acids Res. 1–12 (2013).

1 0

11am Mon Dec 16 talk on integrating middleboxes into software-defined networking
by Jennifer Rexford 14 Dec '13

14 Dec '13

Speaker: Professor Minlan Yu, USC Title: Integrating Middleboxes into Software Defined Networking Date/time: 11am Mon Dec 16 Place: 302 in CS building Abstract: Networks today rely on middleboxes to provide critical performance, security, and policy compliance capabilities. Achieving these benefits and ensuring that the traffic is directed through the desired sequence of middleboxes requires significant manual effort and operator expertise. In this respect, Software-Defined Networking (SDN) offers a promising alternative. Middleboxes, however, introduce new aspects (e.g., policy composition, resource management, dynamic traffic modifications) that fall outside the purvey of traditional L2/L3 functions that SDN supports (e.g., access control or routing). In this talk, we discuss two systems that integrate middleboxes into SDN: First, we propose SIMPLE, which enforces SDN policies with unmodified middleboxes and today’s OpenFlow APIs. Second, we discuss FlowTags, which takes minimal extension of middleboxes to ensure SDN tenets (Origin binding and paths following policy). Bio: Minlan Yu is an assistant professor in the computer science department of University of Southern California. She received her B.A. in computer science and mathematics from Peking University in 2006 and her M.A. and Ph.D in computer science from Princeton University in 2008 and 2011. After that she was a postdoctoral scholar in UC Berkeley for one year. She has actively collaborated with companies such as AT&T, Microsoft, and Bell Labs. Her research interest includes data networking, distributed systems, enterprise and data center networks, network virtualization, and software-defined networking. She received ACM SIGCOMM doctoral dissertation award in 2012 and Google research award in 2013.

1 0

11am Mon Dec 16 talk on integrating middleboxes into software-defined networking
by Jennifer Rexford 14 Dec '13

14 Dec '13

Speaker: Professor Minlan Yu, USC Title: Integrating Middleboxes into Software Defined Networking Date/time: 11am Mon Dec 16 Place: 302 in CS building Abstract: Networks today rely on middleboxes to provide critical performance, security, and policy compliance capabilities. Achieving these benefits and ensuring that the traffic is directed through the desired sequence of middleboxes requires significant manual effort and operator expertise. In this respect, Software-Defined Networking (SDN) offers a promising alternative. Middleboxes, however, introduce new aspects (e.g., policy composition, resource management, dynamic traffic modifications) that fall outside the purvey of traditional L2/L3 functions that SDN supports (e.g., access control or routing). In this talk, we discuss two systems that integrate middleboxes into SDN: First, we propose SIMPLE, which enforces SDN policies with unmodified middleboxes and today’s OpenFlow APIs. Second, we discuss FlowTags, which takes minimal extension of middleboxes to ensure SDN tenets (Origin binding and paths following policy). Bio: Minlan Yu is an assistant professor in the computer science department of University of Southern California. She received her B.A. in computer science and mathematics from Peking University in 2006 and her M.A. and Ph.D in computer science from Princeton University in 2008 and 2011. After that she was a postdoctoral scholar in UC Berkeley for one year. She has actively collaborated with companies such as AT&T, Microsoft, and Bell Labs. Her research interest includes data networking, distributed systems, enterprise and data center networks, network virtualization, and software-defined networking. She received ACM SIGCOMM doctoral dissertation award in 2012 and Google research award in 2013.

1 0

10am Wed Dec 11 talk on pattern matching in compressed HTTP traffic
by Jennifer Rexford 11 Dec '13

11 Dec '13

Speaker: Yaron Koral, Tel Aviv University Title: Efficient multi-pattern matching on Compressed HTTP traffic Date/time: 10-10:50am Wed Dec 11 Place: 402 ’Signature-based’ detection is one of the fundamental technique to detect malicious activities in a network environment. Today, the performance of the security tools is dominated by the speed of the string-matching algorithms that detect these signatures. A significant part of the traffic over the Internet is compressed HTTP. However, current security tools do not deal with such a traffic and require some kind of decompression phase before performing the multi-patterns matching task. Thus, there is a high performance penalty in pattern matching on compressed data. In this talk, we present efficient algorithms for ’on-the-fly’ multi-pattern matching algorithms for common HTTP compression algorithms, such as GZIP and SDCH (Google's compression algorithm). Our results show that surprisingly it is usually faster to do pattern matching on the compressed data, with the penalty of decompression, than to do pattern matching on regular traffic. The talk is based on three papers: one with A. Bremler-Barr (INFOCOM 2009, later in Transactions on Networking 2012), one with Y. Afek and A. Bremler-Barr (Networking 2011, later in Computer Communication 2012) and one with S. Tzur-David, D. Hay and A. Bremler-Barr (INFOCOM 2012).

1 1

Talk starting now in small auditorium
by Jennifer Rexford 09 Dec '13

09 Dec '13

Sent from my iPad

1 0

Colloquium Speaker Yuanyuan Zhou
by Nicole E. Wagenblast 09 Dec '13

09 Dec '13

Do not blame users for misconfigurations Yuanyuan Zhou , University of California, San Diego Monday, December 9, 4:30pm Computer Science 105 Today's data centers usually employ high redundancy to tolerate hardware and software errors. But unfortunately another type of errors, namely configuration errors (i.e., misconfigurations) can still take down the whole data centers. It has contributed to more than 30% high severity issues and caused some of the recent major downtime in cloud service companies including Amazon, Microsoft Azure, Google, Facebook, etc. Unfortunately, many software developers and system designers put most of blames on users for configuration errors, and do not pay enough attention to handling misconfiguration in a more active way. Comparing to software bugs, configuration issues have much less tooling support for error detections, issue tracking, tolerance testing, as well as design reviews. In this talk, I will present our recent work on characterizing misconfigurations in commercial and open source systems (as well as a major commercial cloud service provider), and also some of our solutions in addressing this configuration problem. We approach it from the perspective that configurations are a part of user interface, and thereby need to consider from user perspectives. More specifically, as a practical first step, we need to avoid error-prone requirements and also react gracefully to user mistakes. Our solutions have been used two commercial companies and have influenced some popular open source systems such as "Squid" redesigning their configuration. In this talk, I will also some of the negative interactions (and "challenges") with some open source developers. Yuanyuan Zhou is currently a Qualcomm Chair Professor at UC-San Diego. Before UCSD, she was a tenured associate professor at University of Illinois at Urbana Champaign. Her research interests span the areas of operating systems, software engineering, system reliability and maintainability. She has 3 papers selected into the IEEE Micro Special Issue on Top Picks from Architecture Conferences, best paper at SOSP'05, and 2011 ACM SIGSOFT FSE (Foundation of Software Engineering) Distinguished Paper. She has co-founded two startups. Her recent startup, PatternInsight, has successfully deployed software quality assurance tools in many companies including Cisco, Juniper, Qualcomm, Motorola, Intel, EMC, Lucent, Tellabs, etc. Recently Pattern Insight has sold its Log Insight business to VmWare. In addition, Intel has licensed some of her solutions on detecting concurrency bugs. She has graduated 14 Ph.D. students so far, many of whom have joined top industrial companies and academia such as University of Wisconsin at Madison, University of Toronto, University of Waterloo, etc as tenure-track faculty.

1 1

Fwd: Adi's talk Monday
by Moses S. Charikar 05 Dec '13

05 Dec '13

Adi Shamir will be speaking at IAS this coming Monday, Dec 9. Details below: Cheers, Moses How Cryptosystems Are REALLY Broken Computer Science/Discrete Mathematics Seminar I Topic: How Cryptosystems Are REALLY Broken Speaker: Adi Shamir Affiliation: Weizmann Institute Date: Monday, December 9 Time/Room: 11:15am - 12:15pm/S-101 Most of the cryptosystems we currently use are highly secure, and cannot be broken with reasonable complexity by mathematical cryptanalysis. However, over the last fifteen years researchers have developed many types of physical attacks on their implementations which can easily bypass their mathematical security. In this talk I will survey some of the latest techniques of this type, and show how difficult it is to build a truly secure communication systems.

1 0