Given a k-ary predicate P, a random instance of a constraint satisfaction problem with predicate P (CSP(P)) is a set of m constraints on n variables.  Each constraint is P applied to k random literals. Such an instance is unsatisfiable with high probability when m >> n. Refutation is certifying that a given randomly chosen instance is unsatisfiable. This task has applications in cryptography, hardness of approximation, and learning theory.  This thesis studies refutation using sum-of-squares (SOS) proof systems. SOS is a sequence of increasingly powerful proof systems parameterized by degree: the higher the degree, the more powerful the proof system. On the other hand, finding an SOS proof requires time exponential in the degree.

First, we consider refutation via constant-degree SOS proofs, which can be found in polynomial time.  We show that the number of constraints required for constant-degree SOS refutation of CSP(P) is determined by a complexity parameter C(P), the minimum t for which there is no t-wise uniform distribution over {0,1}^k supported on satisfying assignments to P.  With Allen and O'Donnell, we proved that constant-degree SOS can refute CSP(P) when m = O~(n^{C(P)/2}).  With Kothari, Mori, and O'Donnell, we showed a nearly matching lower bound.

More generally, we consider delta-refutation, certifying that at most a 1-delta fraction of constraints can be simultaneously satisfied.  We also consider SOS proofs with arbitrary, possibly superconstant, degree.  With Allen and O’Donnell, we showed that if every t-wise uniform distribution is delta-far from every distribution supported on satisfying assignments to P, then constant-degree SOS can (delta-o(1))-refute CSP(P) with m = O~(n^{t/2}).  For such P, this can be extended using a result of Raghavendra, Rao, and Schramm to obtain (delta-o(1))-refutation with m = \Delta n constraints via degree-O~(n/Delta^{2/(t-2)}) SOS.  With Kothari, Mori, and O’Donnell, we proved that (delta+o(1))-refutation of CSP(P) with Delta n constraints requires SOS degree Omega~(n/Delta^{2/(t-1)}) when there exists a t-wise uniform distribution that is delta-close to being supported on satisfying assignments to P.  These results establish a three-way trade-off among number of constraints, SOS degree, and refutation strength delta that is tight up to logarithmic factors.

Thesis Committee:
Anupam Gupta (Co-Chair)
Ryan O’Donnell (Co-Chair)
Alan Frieze
Boaz Barak (Harvard University)
Eli Ben-Sasson (Technion -- Israel Institute of Technology)

Livestreaming platforms have become increasingly popular in recent years as a means of sharing and advertising creative content. Popular content streamers who attract large viewership to their live broadcasts can earn a living by means of ad revenue, donations and channel subscriptions. Unfortunately, this incentivized popularity has simultaneously resulted in incentive for fraudsters to provide services to astroturf, or artificially inflate viewership metrics by providing fake live views to customers. Our work provides a number of major contributions: (a) formulation: we are the first to introduce and characterize the viewbot fraud problem in livestreaming platforms, (b) methodology: we propose FLOCK, a principled and unsupervised method which efficiently and effectively identifies botted broadcasts and their constituent botted views, and (c) practicality: our approach achieves over 98% precision in identifying botted broadcasts and over 90% precision/recall against sizable synthetically generated viewbot attacks on a real-world livestreaming workload of over 16 million views and 92 thousand broadcasts. FLOCK successfully operates on larger datasets in practice and is regularly used at a large, undisclosed livestreaming corporation.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

We assume the existence of a one-way permutation exceeds 2^{0.5n}. Such an assumption is supported by decades of cryptanalytic literature, and yet , surprisingly little theory has been developed to exploit this hardness regime. Using birthday simulation, and additional ideas, we show how to overcome impossibility results regarding long-standing protocol problems in the areas of non-malleability and zero-knowledge.

Dakshita Khurana is a PhD student at UCLA working in cryptography. Her interests span many areas of cryptography; she is particularly interested in developing new techniques for achieving secure computation and non-malleability.

Human experts as autonomous agents in a referral network must decide whether to accept a task or refer to a more appropriate expert, and if so to whom. In order for the referral network to improve over time, the experts must learn to estimate the topical expertise of other experts. This thesis extends concepts from Multi-agent Reinforcement Learning and Active Learning to referral networks.

Among a wide array of algorithms evaluated, Distributed Interval Estimation Learning (DIEL), based on Interval Estimation Learning, was found to be promising for learning appropriate referral choices, compared to Greedy, Q-learning, and UCB methods. DIEL's rapid performance gain in the early phase of learning makes it a practically viable algorithm, including when multiple referral hops are allowed. In addition to a synthetic data set, we compare the performance of several top-performing referral algorithms on a referral network of high-performance Stochastic Local Search (SLS) SAT solvers and demonstrate that the referral learning algorithms can learn appropriate referral choices in the real task of solving satisfiability problems where expertise do not obey any known parameterized distribution. Apart from evaluating overall network performance, we conduct a robustness analysis across the learning algorithms, with an emphasis on capacity constraints, evolving networks (i.e. with known experts dropping off and new experts of unknown performance entering), and expertise drift --- situations that often arise in real-world scenarios but largely ignored in the Active Learning literature.

In an augmented learning setting, where experts may report their top skills to their colleagues, we proposed three algorithms, proactive-DIEL, proactive-Q-Learning, and proactive-ε-Greedy. All algorithms exhibited robustness to noisy self-skill estimates and were resilient to evolving networks and strategic misreporting.

Thesis Committee:
Jaime Carbonell (Chair)
Manuel Blum
Manuela Veloso
Victor Lesser (University of Massachusetts, Amherst)

Copy of Thesis Summary

Planning is a problem in Computer Science with many applications. It can be used to automate robotic tasks or beat players in games, for example. However, it has been very difficult coming up with programs that can approximately plan well. Here, we tackle the problem using a different route. We want to see whether we can improve our ability to approximately plan by using quantum mechanics to model classical systems.

The idea of planning using quantum systems may have some merit. Quantum systems make different assumptions than classical systems so to plan in a quantum system, we have to make a new model. By making a new model and planning on it, we increase the scope of problems we can plan on. Also, there is hope that planning in new quantum models might be simpler than in the classical models, especially when we use a compact basis to plan approximately.

We formulate a new quantum model for planning, give some planning algorithms, and show some experimental results, assuming only elementary knowledge in linear algebra. To formulate a new quantum model and planning, we review discrete quantum mechanics to get an understanding about how quantum systems work. Then, we derive the QuaMDP planning model and show one way to plan in it. We also show one way to generate QuaMDP models from a dynamical system, given its potential energy function. Then, we test how well our algorithms can approximately plan on this new model to find inherent weaknesses and strengths.

Thesis Committee:
Geoff Gordon
Gary Miller

Copy of MS Thesis Document

Programmers, like pen-and-paper mathematicians, often seek to define new syntactic sugar that lowers the syntactic cost of common idioms. Unfortunately, the most direct mechanisms of syntactic control available to programmers do not support modular reasoning about determinism (i.e. separately defined forms can conflict syntactically with one another), and they obscure the type and binding structure of the program. We argue therefore that these mechanisms are unreasonable for programming "in the large". Typed term-rewriting macro systems (e.g. as available in Scala) are more reasonable, but afford programmers limited syntactic control.

This thesis formally describes typed syntax macros (TSMs), which give library providers programmatic control over both the parsing and expansion of expressions and patterns of generalized literal form at a specified type or parameterized family of types. Expansion is strictly hygienic, meaning that 1) expansions can refer to external bindings only via spliced terms or supplied module parameters; and 2)  expansions do not reveal internal bindings to spliced terms or to the remainder of the program. We argue that this mechanism occupies a "sweet spot" in the design space, in that it captures many common syntactic idioms while avoiding the problem of syntactic conflicts by construction and supplying clients with clear abstract reasoning principles.

Thesis Committee:
Jonathan Aldrich (Chair)
Robert Harper
Karl Crary
Eric Van Wyk (University of Minnesota)

I will explain the cheat sheet technique in query complexity, and show how to use it to get a power 2.5 separation between classical and quantum computation (beating the quadratic speedup of Grover search). I'll then discuss the connections between query and communication complexity, and present recent applications of the cheat sheet technique in the communication complexity setting.

Shalev Ben-David is a PhD student in his last year at MIT.

Supported in part by the Simons Foundation

Video recording

The spectra of signed matrices have played a fundamental role in social sciences, graph theory and control theory. They have been key to understanding balance in social networks, to counting perfect matchings in bipartite graphs, and to analyzing robust stability of dynamic systems involving uncertainties. More recently, the results of Marcus et al. have shown that an efficient algorithm to find a signing of a given adjacency matrix that minimizes the largest eigenvalue could immediately lead to efficient construction of Ramanujan expanders.

Motivated by these applications, this talk investigates natural spectral properties of signed matrices and address the computational problems of identifying signings with these spectral properties. There are three main results we will talk about: (a) NP-completeness of three signing related problems with (negative) implications to efficiently constructing expander graphs, (b) a complete characterization of graphs that have all their signed adjacency matrices be singular, which implies a polynomial-time algorithm to verify whether a given matrix has a signing that is invertible, and (c) a polynomial-time algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible signing.

About the Speaker

Mechanized reasoning has proved effective in avoiding serious mistakes in software and hardware, and yet remains unpopular in the practice of mathematics. My thesis is aimed at making mechanization easier so that more mathematicians can benefit from this technology. Particularly, I experimented with higher-dimensional types, an extension of ordinary types with a hierarchy of stacked relations, and managed to mechanize many important results from classical homotopy theory in the proof assistant Agda. My work thus suggests higher-dimensional types may help mechanize mathematical concepts.

Thesis Committee:
Robert Harper (Chair)
Frank Pfenning
Jeremy Avigad
Andrej Bauer (Univerza v Ljubljani)
Ulrik Buchholtz (Technische Universität Darmstadt)
Daniel R. Licata (Wesleyan University)


Subscribe to CSD