Skip to main content
Add to Calendar
2018-08-16 10:00:00
2018-08-16 11:00:00
America/New_York
Thesis Defense: Below P vs NP: Fine-Grained Hardness for Big Data Problems
Abstract: The theory of NP-hardness has been remarkably successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial-time algorithms, but large exponents in their runtime bounds can make them inefficient in practice. For example, quadratic-time algorithms, although practical on moderately sized inputs, can become inefficient on big data problems that involve gigabytes or more of data. Although for many data analysis problems no sub-quadratic time algorithms are known, any evidence of quadratic-time hardness has remained elusive. In this thesis we present hardness for several text analysis and machine learning tasks:* Lower bounds for edit distance, regular expression matching and other pattern matching and string processing problems.* Lower bounds for empirical risk minimization such as kernel support vectors machines and other kernel machine learning problems.All of these problems have polynomial time algorithms, but despite extensive amount of research, no near-linear time algorithms have been found. We show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. We also show how these lower bounds have inspired the development of efficient algorithms for some variants of these problems.
32-D463 (Star)
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-12 16:00:00
2018-09-12 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-13 13:00:00
2018-09-13 14:00:00
America/New_York
Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution
ABSTRACT:TBASPEAKER BIO:Ofir is a Ph.D. candidate at the University of Michigan. His current research focuses on the feasibility of secure execution in the cloud. His recent publications include HotCalls (ISCA 2017) and WALNUT (EuroS&P 2017). Ofir worked for Intel in Haifa as a security researcher in the SGX group. He received his Master's in Computer Engineering from Tel-Aviv University and B.Sc from the Technion. His previous research focused on differential power analysis of cryptographic devices, which was published in CHES and HASP.
32-G449
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-13 13:00:00
2018-09-13 14:00:00
America/New_York
Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution
ABSTRACT: TBASPEAKER BIO:Ofir is a Ph.D. candidate at the University of Michigan. His current research focuses on the feasibility of secure execution in the cloud. His recent publications include HotCalls (ISCA 2017) and WALNUT (EuroS&P 2017). Ofir worked for Intel in Haifa as a security researcher in the SGX group. He received his Master's in Computer Engineering from Tel-Aviv University and B.Sc from the Technion. His previous research focused on differential power analysis of cryptographic devices, which was published in CHES and HASP.
32-G449
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-13 13:00:00
2018-09-13 14:00:00
America/New_York
Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution
ABSTRACT:TBASPEAKER BIO:Ofir is a Ph.D. candidate at the University of Michigan. His current research focuses on the feasibility of secure execution in the cloud. His recent publications include HotCalls (ISCA 2017) and WALNUT (EuroS&P 2017). Ofir worked for Intel in Haifa as a security researcher in the SGX group. He received his Master's in Computer Engineering from Tel-Aviv University and B.Sc from the Technion. His previous research focused on differential power analysis of cryptographic devices, which was published in CHES and HASP.
32-G449
Belfer
sarah_donahue@hks.harvard.edu
TBA
Percy Liang
Stanford University
Add to Calendar
2018-09-19 16:00:00
2018-09-19 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-26 16:00:00
2018-09-26 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-09-26 16:30:00
2018-09-26 17:30:00
America/New_York
Learning Using Statistical Invariants (Revision of Machine Learning Problem)
Abstract:In this talk I will introduce a new learning paradigm, called Learning Using Statistical Invariants (LUSI), which is different from the classical one. In the classical paradigm, the learning machine using observations, constructs a classification rule that minimizes the probability of expected error; it is data-driven model of learning. In the LUSI paradigm, in order to construct the desired classification function, the learning machine first, using data, computes statistical invariants that are specific for the problem, and then minimizes the expected error in a way that preserve these invariants; it is thus both data- and intelligent-driven learning.From a mathematical point of view, methods of the classical paradigm employ mechanisms of strong convergence of approximations to the desired function, whereas methods of the new paradigm employ both strong and weak convergence mechanisms. This can significantly increase the rate of convergence. The main part of the talk is content of paper published in Machine Learning, Springer 2018. LUSI describes complete theory of learning and can be considered as a mathematical alternative to "deep learning" heuristic.Bio:Professor Vapnik has taught and researched in computer science, theoretical and applied statistics for over 30 years. He has published six monographs and over 100 research papers. His major achievements have been the development of a general theory of minimizing the expected risk using empirical data, and a new type of learning machine called Support Vector machine that possesses a high level of generalization ability. These techniques have been used to solve many pattern recognition and regression estimation problems and have been applied to the problems of dependency estimation, forecasting, and constructing intelligent machines. Prof. Vladimir Vapnik gained his Masters Degree in Mathematics in 1958 at Uzbek State University, Samarkand, USSR. Vapnik received his master's degree in mathematics from the Uzbek State University in 1958, and Ph.D in statistics at the Institute of Control Sciences, Moscow in 1964, where he worked from 1961 to 1990 and became Head of the Computer Science Research Department. He then joined AT&T Bell Laboratories, Holmdel, NJ.Vapnik and his colleagues at AT&T developed the theory of the support vector machine and demonstrated its performance on a number of problems of interest to the machine learning community, including handwriting recognition. The group later became the Image Processing Research Department of AT&T Laboratories when AT&T spun off Lucent Technologies in 1996. In 2000, Vapnik and neural networks expert, Hava Siegelmann developed Support Vector Clustering, which enabled the algorithm to categorize inputs without labels - becoming one of the most ubiquitous data clustering applications in use. Vapnik left AT&T in 2002 and joined NEC Laboratories in Princeton, New Jersey. He also holds a Professor of Computer Science and Statistics position at Royal Holloway, University of London since 1995, as well as a position as Professor of Computer Science at Columbia University, New York City since 2003.His current research is presented in his latest books "Statistical Learning Theory", Wiley, 1998, and "The Nature of Statistical Learning Theory", second edition, Springer, 2000.
32-123/Kirsch Auditorium
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-10-03 16:00:00
2018-10-03 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-10-10 16:00:00
2018-10-10 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-10-17 16:00:00
2018-10-17 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-10-24 16:00:00
2018-10-24 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
TBA
Emma Brunskill
Stanford University
Add to Calendar
2018-10-31 16:00:00
2018-10-31 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-11-07 16:00:00
2018-11-07 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-11-14 16:00:00
2018-11-14 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-11-21 16:00:00
2018-11-21 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-11-28 16:00:00
2018-11-28 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
Add to Calendar
2018-12-12 16:00:00
2018-12-12 17:00:00
America/New_York
TBA
Belfer
sarah_donahue@hks.harvard.edu
