Back to Events

Seminar Series

July 05

Harry Lang: Coresets for k-Means-Type Problems on Streams

Harry Lang
Johns Hopkins University

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-07-05 16:00:00 2017-07-05 17:00:00 America/New_York Harry Lang: Coresets for k-Means-Type Problems on Streams Abstract: Let f be a non-negative symmetric dissimilarity measure. Given sets of points P (the input data) and C (a "query"), we define F(P,C) = \sum_{p \in P} \min_{c \in C} f(p,c). An example that fits into this framework is k-means clustering where f = distance^2 and we restrict |C| = k.An $\epsilon$-coreset for P is a set Q such that F(Q,C) is within a factor of $(1 + \epsilon)$ of F(P,C) for any query C. For data reduction, the goal is to construct a coreset Q of minimal cardinality. We introduce improved coreset constructions for a wide class of functions that obey a weak form of the triangle inequality: this includes k-means, k-median, Tukey's bi-weight function, and the Huber loss function.In the streaming model, the input P (a set of n points) arrives sequentially and algorithms attempt to maintain a coreset using a minimal amount of memory. We introduce a new technique for maintaining coresets in the streaming model with O(1) overhead. For example, the previous state-of-the-art for maintaining an $\epsilon$-coreset for metric k-means on a stream required the storage of $O(\epsilon^{-4} k \log k \log^6 n)$ points whereas our method requires $O(\epsilon^{-2} k \log k \log n)$ points.Joint work with Vladimir Braverman and Dan Feldman. 32-G575

May 31

Talk: Andrea Lincoln:Conditional Hardness for Sensitivity Problems

Andrea Lincoln
CSAIL MIT

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-05-31 16:00:00 2017-05-31 17:00:00 America/New_York Talk: Andrea Lincoln:Conditional Hardness for Sensitivity Problems Abstract: In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity.In this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible.We further show under the BMM conjecture that many problems, such as approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We further give a reduction from All Pairs Shortest Paths to Diameter under 1 deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required.Joint work with: Monika Henzinger, Stefan Neumann and Virginia Vassilevska Williams. 32-G575

May 24

Talk: Cell-Probe Lower Bounds from Online Communication Complexity

Josh Alman
CSAIL MIT

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-05-24 16:00:00 2017-05-24 17:00:00 America/New_York Talk: Cell-Probe Lower Bounds from Online Communication Complexity Abstract: In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. This model has a closer and more natural correspondence to dynamic data structures than the classic communication models do and hence presents a new perspective on data structures.We first present a lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. Then we apply the online communication model to data structure lower bounds by studying the Group Range Problem, a dynamic data structure problem. This problem admits an O(log n)-time worst-case data structure. Using online communication complexity, we prove a tight cell-probe lower bound: spending o(log n) (even amortized) time per operation results in at best an exp(-\delta^2 n) probability of correctly answering a (1/2 + \delta)-fraction of the n queries.Joint work with Joshua Wang and Huacheng Yu. 32-G575

May 11

Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds

Arnab Bhattacharyya
IISc

Part Of

2:00P
- 3:00P

Location

32-G575
Add to Calendar 2017-05-11 14:00:00 2017-05-11 15:00:00 America/New_York Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds Abstract:We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs), assuming Khot's Unique Games Conjecture (UGC). In particular, we prove that for any constants d in? the positive integers? and eps > 0, assuming the UGC, it is NP-hard to decide: given a set of {-1,1}-labeled points in R^n whether (YES Case) there exists a halfspace that classifies (1-eps)-fraction of the points correctly, or (NO Case) any degree-d PTF classifies at most (1/2 + eps)-fraction of the points correctly.This strengthens to all constant degrees the previous NP-hardness of learning using degree-2 PTFs shown by Diakonikolas et al. (2011). The latter result had remained the only progress over the works of Feldman et al. (2006) and Guruswami et al. (2006) ruling out weakly proper learning adversarially noisy halfspaces.Joint work with Suprovat Ghoshal (IISc) and Rishi Saket (IBM). 32-G575

May 10

Relaxed Locally Correctable Codes

Govind Ramnarayan
CSAIL MIT

Part Of

4:00P
- 5:00P

Location

32-D463
Add to Calendar 2017-05-10 16:00:00 2017-05-10 17:00:00 America/New_York Relaxed Locally Correctable Codes Abstract: Locally decodable codes (resp. locally correctable codes), or LDCs (resp. LCCs), are codes for which individual symbols of the message (resp. codeword) can be recovered by reading just a few bits from a noisy codeword. Such codes have been very useful in theory and practice, but suffer from a poor tradeoff between the rate of the code and the query complexity of its local decoder (resp. corrector).A natural relaxation of locally decodable codes (LDCs) considered by Ben-Sasson et al. (SICOMP, 2006) allows the decoder to "reject" when it sees too many errors to decode the desired symbol of the message. They show that, when the decoder is given this liberty, there exist codes with rate that is subexponentially better than that of the best constant-query locally decodable codes known today.We extend their relaxation to locally correctable codes, and achieve similar savings in complexity compared to existing LCCs. Specifically, our codes have:1. Subexponentially lower rate than existing LCCs in the constant-query regime.2. Nearly subexponentially lower query complexity than existing LCCs in the constant-rate regime.Joint work with Tom Gur and Ron Rothblum. 32-D463

April 20

Approximate Modularity Revisited

Inbal Talgam-Cohen
Hebrew University

Part Of

4:00P
- 5:00P

Location

Seminar Room G575
Add to Calendar 2017-04-20 16:00:00 2017-04-20 17:00:00 America/New_York Approximate Modularity Revisited Set functions with convenient properties (such as submodularity) often arise in algorithmic game theory, and allow for improved properties of optimization algorithms and mechanisms. It is natural to ask (e.g., in the context of data driven applications) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions. One question that we address is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive (in a precise formal sense) as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem. Another question that we address is that of how to learn a linear function $h$ that is close to an approximately linear function $f$, while querying the value of $f$ on only a small number of sets. Joint work with Uriel Feige and Michal Feldman. Seminar Room G575

April 18

April 12

New separations of formula vs. circuit size

Ben Rossman
U. Toronto

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-04-12 16:00:00 2017-04-12 17:00:00 America/New_York New separations of formula vs. circuit size Abstract: I will present some recent results on the power of formulas vs. circuits in the bounded-depth setting. In joint work with Srikanth Srinivasan, we obtain a nearly optimal separation between the AC^0[?] formula vs. circuit size of the Approximate Majority function. In other work, we show that the AC^0 circuit (resp. formula) size of the H-Subgraph Isomorphism problem is tied to the treewidth (resp. treedepth) of the pattern graph H. The latter formula-size lower bound relies on a new “excluded-minor approximation” of treedepth (joint with Kenich Kawarabayashi). The former is based on an improved construction of low-degree approximating polynomials for AC^0[?] formulas. 32-G575

April 06

A Probabilistic Theory of Deep Learning

Richard Baraniuk
Rice University

Part Of

3:00P
- 4:00P

Location

32-D463 (Star)
Add to Calendar 2017-04-06 15:00:00 2017-04-06 16:00:00 America/New_York A Probabilistic Theory of Deep Learning Abstract:A grand challenge in machine learning is the development of computational algorithms that match or outperform humans in perceptual inference tasks that are complicated by nuisance variation. For instance, visual object recognition involves the unknown object position, orientation, and scale in object recognition while speech recognition involves the unknown voice pronunciation, pitch, and speed. Recently, a new breed of deep learning algorithms have emerged for high-nuisance inference tasks that routinely yield pattern recognition systems with near- or super-human capabilities. But a fundamental question remains: Why do they work? Intuitions abound, but a coherent framework for understanding, analyzing, and synthesizing deep learning architectures has remained elusive. We answer this question by developing a new probabilistic framework for deep learning based on the Deep Rendering Model: a generative probabilistic model that explicitly captures latent nuisance variation. By relaxing the generative model to a discriminative one, we can recover two of the current leading deep learning systems, deep convolutional neural networks and random decision forests, providing insights into their successes and shortcomings, a principled route to their improvement, and new avenues for exploration.Speaker Bio. Richard G. Baraniuk is the Victor E. Cameron Professor of Electrical and Computer Engineering at Rice University. His research interests lie in new theory, algorithms, and hardware for sensing, signal processing, and machine learning. He is a Fellow of the IEEE, AAAS, and the National Academy of Inventors and has received the DOD Vannevar Bush Faculty Fellowship (NSSEFF), national young investigator awards from the US NSF and ONR, the Rosenbaum Fellowship from the Isaac Newton Institute of Cambridge University, the ECE Young Alumni Achievement Award from the University of Illinois, the Wavelet Pioneer and Compressive Sampling Pioneer Awards from SPIE, the IEEE Signal Processing Society Best Paper Award, and the IEEE Signal Processing Society Technical Achievement Award. His work on the Rice single-pixel compressive camera has been widely reported in the popular press and was selected by MIT Technology Review as a TR10 Top 10 Emerging Technology. For his teaching and education projects, including Connexions (cnx.org) and OpenStax (openstax.org), he has received the C. Holmes MacDonald National Outstanding Teaching Award from Eta Kappa Nu, the Tech Museum of Innovation Laureate Award, the Internet Pioneer Award from Harvard University, the World Technology Award for Education, the IEEE-SPS Education Award, the WISE Education Award, and the IEEE James H. Mulligan, Jr. Medal for Education. 32-D463 (Star)

April 05

Fifty Shades of Adaptivity (in Property Testing)

Clement Canonne
Columbia University

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-04-05 16:00:00 2017-04-05 17:00:00 America/New_York Fifty Shades of Adaptivity (in Property Testing) Abstract: Adaptivity is known to play a crucial role in property testing. Inparticular, there exist properties for which there is an exponential gapbetween the power of /adaptive/ testing algorithms, wherein each querymay be determined by the answers received to prior queries, and their/non-adaptive/ counterparts, in which all queries are independent ofanswers obtained from previous queries.In this work, we investigate the role of adaptivity in property testingat a finer level. We first quantify the degree of adaptivity of atesting algorithm by considering the number of "rounds of adaptivity" ituses. More accurately, we say that a tester is k-(round) adaptive if itmakes queries in k+1 rounds, where the queries in the i'th round maydepend on the answers obtained in the previous i-1 rounds. Then, we askthe following question:Does the power of testing algorithms smoothly grow with the number ofrounds of adaptivity?We provide a positive answer to the foregoing question by proving anadaptivity hierarchy theorem for property testing. Specifically, ourmain result shows that for every integer n and 0 <= k <= n^{0.33} thereexists a property P_{n,k} of functions for which (1) there exists ak-adaptive tester for P_{n,k} with query complexity ~O(k), yet (2) any(k-1)-adaptive tester for P_{n,k} must make ~Omega(n/k^2) queries. Inaddition, we show that such a qualitative adaptivity hierarchy can bewitnessed for testing natural properties of graphs.Joint work with Tom Gur (Weizmann Institute). 32-G575

March 30

Ben Rossman:New Separations of Formula vs. Circuit Size

Ben Rossman
U. Toronto

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-03-30 16:00:00 2017-03-30 17:00:00 America/New_York Ben Rossman:New Separations of Formula vs. Circuit Size I will present some recent results on the power of formulas vs. circuits in the bounded-depth setting. In joint work with Srikanth Srinivasan, we obtain a nearly optimal separation between the AC^0[?] formula vs. circuit size of the Approximate Majority function. In other work, we show that the AC^0 circuit (resp. formula) size of the H-Subgraph Isomorphism problem is tied to the treewidth (resp. treedepth) of the pattern graph H. The latter formula-size lower bound relies on a new “excluded-minor approximation” of treedepth (joint with Kenich Kawarabayashi). The former is based on an improved construction of low-degree approximating polynomials for AC^0[?] formulas. 32-G575

March 15

Explicit two-source extractors for near-logarithmic min-entropy

Dean Doron
Tel-Aviv University

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-03-15 16:00:00 2017-03-15 17:00:00 America/New_York Explicit two-source extractors for near-logarithmic min-entropy Abstract:In this talk, we show an explicit construction of extractors for two independent sources of near-logarithmic min-entropy.Previous constructions required either polylog(n) min-entropy or more than two sources.The result extends the breakthrough result of Chattopadhyay and Zuckerman and also uses non-malleable extractors.The main new ingredient is a somewhere-random condenser with a small entropy gap, used as a sampler.Our construction can be seen as an efficient reduction to constructing non-malleable extractors, so using very recent constructions of non-malleable extractors (by Cohen and Li) - we will see how to obtain explicit two-source extractor for O(log n loglog n) min-entropy and constant error. 32-G575

March 02

Twenty (simple) questions

Yuval Filmus
Technion, Israel

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-03-02 16:00:00 2017-03-02 17:00:00 America/New_York Twenty (simple) questions Abstract: The game of 20 questions is a search-theoretic interpretation of entropy.Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average. However, it might invoke arbitrary Yes/No questions. Are there restricted sets of questions that match the optimal strategy, either exactly or approximately?We explore this question from several different angles, uncovering a connection to binary comparison search trees, a variant of binary search trees.Joint work with Yuval Dagan, Ariel Gabizon and Shay Moran, to appear in STOC 2017. 32-G575

March 01

Opting Into Optimal Matchings

Nika Haghtalab
Carnegie Mellon University (CMU)

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-03-01 16:00:00 2017-03-01 17:00:00 America/New_York Opting Into Optimal Matchings Abstract: Kidney transplant is sometimes the best treatment for people who suffer from chronic kidney disease. However, due to medical incompatibility issues, a direct kidney transplant is not always possible even for those patients that are fortunate enough to have a willing donor. This is where Kidney Exchange comes in: It enables two or more donor-patient pairs to swap donors, so that each patient receives a compatible kidney. In recent years, hospitals have enrolled patients into regional or even national kidney exchange programs. However, hospitals may choose not to participate if they can match more of their own patients on their own -- economists would say that the exchange is not individually rational for hospitals. This behavior significantly reduces the social welfare -- the total number of patients that receive a kidney transplant.In this work, we revisit the problem of designing optimal, individually rational kidney exchange mechanisms. We offer a new perspective on this problem by showing that under mild probabilistic assumptions, any optimal kidney exchange is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms.This talk is based on joint work with Avrim Blum, Ioannis Caragiannis, Ariel Procaccia, Eviatar Procaccia, and Rohit Vaish (SODA'17). 32-G575