New computing platforms have greatly increased the demand for programmers, but learning to program remains a big challenge. Program synthesis has the potential to revolutionize programming by making it more accessible. My work has focused on two goals: making programming more intuitive through the use of new interfaces, and using automated feedback to help students learn programming. In this talk, I will present my work on three systems that work towards these goals.
The growth of computer science enrollments, especially in introductory courses, raises the possibility of increasing levels of plagiarism. Fortunately, good software plagiarism detectors have been available since the mid-90's, and these help detect suspicious assignment submissions. However, many popular plagiarism detectors were designed when computer memories were two to three orders of magnitude smaller than today's systems, so these systems necessarily made a number of assumptions to bound their running times and keep their memory consumption low.
This talk gives an introduction to a recently established link between the geometry of numbers and mixed integer linear optimization. The main focus is to provide a review of families of lattice-free polyhedra and their use in the context of deriving and explaining cutting planes for mixed integer programs. This approach is not only mathematically interesting, but it leads to some fundamental new discoveries, such as an understanding under which conditions cutting planes algorithms converge finitely.
Multicore is here to stay. Software developers are moving to concurrent programming. However, this move is slow and challenging due to the exponential complexity in reasoning about concurrency. In particular, Heisenbugs such as data races, which are non-deterministic concurrency errors, pervasively infect concurrent software, making concurrent program debugging notoriously difficult.
Commitee: Stephen Wright (advisor), James Luedtke (advisor), Jeffrey Linderoth (advisor), Thomas Rutherford, Christopher Re (Stanford University)
In this dissertation we study several nonconvex and combinatorial optimization problems with applications in production planning, machine learning, advertising, statistics, and computer vision. The common theme is the use of algorithmic and modelling techniques from mixed-integer program- ming (MIP) which include formulation strengthening, decomposition, and linear programming (LP) rounding.
Noisy and missing data are prevalent in many real-world statistical estimation problems. Popular techniques for handling non-idealities in data, such as imputation and expectation-maximization, are often difficult to analyze theoretically and/or terminate in local optima of non-convex functions -- these problems are only exacerbated in high-dimensional settings. We present new methods for obtaining high-dimensional regression estimators in the presence of corrupted data, and provide theoretical guarantees for the statistical consistency of our methods.
In recent years online learning (sequential prediction) has received much attention as it often produces fast and simple learning algorithms that enjoy robustness to changing or even adversarial data sources. However, despite the extensive existing literature on online learning, our theoretical understanding of the framework has been rather lacking. Most existing analyses have been case by case, and there is a lack of a general theory and methodology for designing online learning algorithms for the problem at hand.
Modern wireless technology enables the vision of future large scale systems such as the SmartGrid, a network of ubiquitous and heterogeneous devices wirelessly connected to the Internet, and wireless health monitoring and health modifying sensor networks over communities and not just individuals. All of these applications necessitate methods that simultaneously consider scale, communication, sensing and control. In this talk, key elements of realizing this vision are examined.