Timings : Wednesdays, 11:00 am - 12:00 am
Venue : CoRE 301A
The talk on December 9 will be held in CoRE 431.
Organizers : Eric Allender, Michael Saks and Mario Szegedy
Seminar webpages for previous semesters can be found here.
Consider the following setting. Suppose we are given as input a "corrupted" truth-table of a polynomial f(x1,..,xm) of degree r = o(sqrt(m)), with a random set of 1/2 - o(1) fraction of the evaluations flipped. Can the polynomial f be recovered? Turns out we can, and we can do it efficiently!
The above question is a demonstration of the reliability of Reed-Muller codes under the random error model. For Reed-Muller codes over F2, the message is thought of as an m-variate polynomial of degree r, and its encoding is just the evaluation over all of F2^m.
In this talk, we shall study the resilience of RM codes in the *random error* model. We shall see that under random errors, RM codes can efficiently decode many more errors than its minimum distance. (For example, in the above toy example, minimum distance is about 1/2^{sqrt(m)} but we can correct close to 1/2-fraction of random errors). This builds on a recent work of [Abbe-Shpilka-Wigderson-2015] who established strong connections between decoding erasures and decoding errors. The main result in this talk would be constructive versions of those connections that yield efficient decoding algorithms.
This is joint work with Amir Shpilka and Ben Lee Volk.Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are special families of error-correcting codes that admit highly efficient sub-linear time algorithms for error correction and detection, respectively, while making a small number of queries to the received word.
LCCs and LTCs were originally studied in complexity theory because of their close relationship to program checking and probabilistically-checkable proofs (PCPs), but in recent years there has been a new incentive for their study due to their potential use for massive data transmission and storage purposes and the successful implementation of related families of local codes in cloud storage systems.
We show constructions of LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial number of queries and running time of the form $exp(sqrt{log n})$ where n is the codeword length. Prior to our work, such codes were known to exist only with polynomial number of queries and running time of the form $n^{beta}$ and there were several, quite different, constructions known.
Along the way, we also construct LCCs and LTCs over large (but constant) size alphabets, with the same number of queries and running time, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. Such a result was previously not known for any sub-linear number of queries and running time.
If time permits I will also discuss a very recent work that improves the running time and number of queries of LTCs to a quasi-polylogarithmic function of the form $(log n)^{O(log log n)}$.
Joint work with Swastik Kopparty, Or Meir and Shubhangi SarafTrue randomness is indispensable for every natural science where numerical simulations are performed, and is also of paramount important for secure communication. Obtaining true random bits is a difficult process, one that must reply on uncertain events. We take a non-standard view of Big Data, viewing them as big sources of low quality randomness.
Now, the problem is to extract true uniform random bits out of big data. For this we develop the first streaming extractor for sources of linear min-entropy, circumventing a number of provable limitations that include a general impossibility result by Bar-Yosef, Reingold, Shatiel, and Trevisan. New techniques and tools are developed towards proving that this extractor works. The extractor itself is perhaps the conceptually simplest generic extractor.
We implement our extractor as a streaming algorithm and we run a very extensive empirical validation study. Before our work randomness extraction was a vastly theoretical area of study. No known extractor could work in practice on statistical sources of moderate size, in the sense that a few 1,000s of years were needed for such extraction, where on sources of size about 20GBs a conservatively estimated running time exceeds 100,000 years. In this sense, our extractor is the first practical such construction.
This is joint work with Guang Yang and David Woodruff.This talk will focus on the problem of learning halfspaces in the presence of noise. I will describe recent results for this problem under various noise models ranging from the notorious malicious noise model of Valiant to the more realistic Massart noise model studied in statistical learning theory. In the malicious noise model, an adversary can corrupt an η fraction of both the label part and the feature part of an example. In the Massart noise model, the label of each example can be flipped with a probability upper bounded by a constant less than half. For the malicious noise model we design a polynomial-time algorithm for learning halfspaces in R^d under the uniform distribution with near optimal noise tolerance. We also provide the first efficient algorithm for learning linear separators under the Massart noise model when the underlying distribution is uniform.
Our results also imply the first active learning algorithm for learning halfspaces that can handle near optimal noise.
Based on joint work with Nina Balcan, Nika Haghtalab, Phil Long and Ruth Urner.We show a new approach to the approximate near neighbor problem, which improves upon the classic Locality Sensitive Hashing (LSH) scheme. Our new algorithms obtain query time (roughly) quadratically better than the optimal LSH algorithms of [Indyk-Motwani'98] for the Hamming space, and [Andoni-Indyk'06] for the Euclidean space. For example, for the Hamming space, our algorithm has query time n^r and space n^{1+r}, where r=1/(2c-1)+o(1) for c-approximation. Our algorithms bypass the lower bounds for LSH from [O’Donnell-Wu-Zhou'11].
The new approach is based on hashing that itself depends on the given pointset. In particular, one of the main components is a procedure to decompose an arbitrary pointset into several subsets that are, in a certain sense, pseudo-random. Our data-dependent hashing scheme is optimal.
Based on a few joint papers with Piotr Indyk, Huy Nguyen, and Ilya Razenshteyn.We consider the problem of approximating frequency moments in the streaming model. Given a stream D = {p_1,p_2,...,p_m} of numbers from {1,...,n}, a frequency of i is defined as f_i = |{j: p_j = i}|. The k-th frequency moment of D is defined as F_k = \sum_{i=1}^n f_i^k. In their celebrated paper, Alon, Matias, and Szegedy (STOC 1996) introduced the problem of computing a (1 +/- epsilon)-approximation of F_k with sublinear memory. We give upper bound of O(n^{1-2/k}) bits that matches, up to a constant factor, the lower bound of Woodruff and Zhang (STOC 12) for constant epsilon and k > 3 (joint work with Jonathan Katzman, Charles Seidell and Gregory Vorsanger, APPROX 14).
If time permits, we will present some recent results on universal sketches (joint works with Alan Roytman and Rafail Ostrovsky, RANDOM 15, and Stephen Chestnut, RANDOM 15), and k-median clustering on sliding windows (joint work Harry Lang, Keith Levin and Morteza Monemizadeh, SODA 16, FSTTCS 16).
It is known from the works of Lovett-Meshulam-Samrodnitsky, Tao-Ziegler, and more recently, Bhowmick-Lovett, that there are Boolean functions which do not correlate well with classical polynomials of a certain degree but have good correlation with some non-classical polynomial of the same degree.
Noting that the notion of approximation is different from that of correlation in the case of non-classical polynomials, Bhowmick and Lovett asked the following questions:
* Do non-classical polynomials of degree \sqrt{n} approximate the majority function better than classical polynomials of the same degree?
* Is there any Boolean function for which non-classical polynomials offer an advantage over classical polynomials in the case of approximation?
We give a negative answer to the first question. We do so by studying polynomials over rings of the form Z/p^kZ and observing that non-classical polynomial are a special case of such polynomials. Our proof essentially involves proving bounds for "weak representations" of the majority function over Z/p^kZ, strengthening classical results of Szegedy and Smolensky.
For the second question, we give a positive answer by showing that elementary symmetric polynomials of a suitable degree are well approximated by non-classical polynomials.
Joint work with Prahladh Harsha and Srikanth Srinivasan.In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials over finite fields shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) allow one to ``refine'' a given collection of polynomials to a new collection of polynomials that are ``pseudorandom''.
We discuss algorithmic versions of these regularity lemmas and give two applications. We show that Reed-Muller codes can be globally decoded at any error rate (even beyond list-decoding radius) if we assume that the noise is ``structured''. As another application, we give an efficient algorithm for finding prescribed decompositions of low-degree polynomials.
Lastly, we discuss structure theorems for low-degree polynomials. Let \F=\F_p be a prime field. Haramaty and Shpilka [STOC 2010] proved that a biased cubic or quartic polynomial f \in \F[x_1,...,x_n] can be written in the form f= g_1h_1+...+g_t h_t (as a function), where t depends only on the bias of f, and g_i and h_i are degree < deg(f) polynomials satisfying deg(g_i)+deg(h_i)\leq deg(f). Using regularity lemmas for polynomials, we prove that such a strong structure theorem holds for degree five polynomials as well. This structure theorem implies that every biased degree five polynomial is constant on an Omega(n) dimensional subspace of \F^n.
We study the problem of allocating a set of indivisible items among agents with additive valuations with the goal of maximizing the geometric mean of the agents’ valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is unbounded, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation.
An interesting contribution of this work is the fractional allocation that we use. The relaxation of our problem can be solved efficiently using the Eisenberg-Gale program, whose optimal solution can be interpreted as a market equilibrium with the dual variables playing the role of item prices. Using this market-based interpretation, we define an alternative equilibrium allocation where the amount of spending that can go into any given item is bounded, thus keeping the highly priced items under-allocated, and forcing the agents to spend on lower priced items. The resulting equilibrium allocation reveals more information regarding how to assign items so as to obtain a good integral allocation.
Joint work with Richard Cole; appeared in STOC 2015.
In this talk, I will present techniques that combine optimization and learning for decision making in complex, uncertain, online environments. Much of this work is motivated by challenges faced in modern revenue management problems, namely, a) unknown or difficult to estimate demand distributions, b) multiple complex nonlinear constraints and objectives, c) the need for fast large-scale algorithms, and d) personalized decisions. Formulating these problem aspects into an "online stochastic convex programming" framework, we devise fast algorithms that combine primal-dual paradigm with online learning to achieve provably optimal performance bounds. When applied to the special case of online packing, our ideas yield simpler and faster algorithms with optimal competitive ratio for this widely studied problem.
I will further discuss a "bandit" property present in many revenue management problems, where the uncertain demand at each point in time is determined by the decision, and can only be observed "after" taking the decision. For example, in pay-per-click revenue model in internet advertising, a click (or no click) on an ad can be observed only after the ad is selected and displayed in response to the user query. Similar situations occur in many other applications including posted-price based revenue management, worker-task allocation problem in crowdsourcing, machine scheduling, sensor network management etc. Modeling this problem as a combination of the classic multi-armed bandit problem and online stochastic convex programming, we design algorithms that balance the inherent exploration-exploitation tradeoff to achieve asymptotically optimal regret bounds. Our results significantly improve upon several known results in online linear programming and multi-armed bandits literature, and reveal many interesting connections between convex optimization algorithms, Fenchel duality, multi-armed bandits and online learning.
This talk is based on joint work with Nikhil R. Devanur.
In this talk, we will discuss yet another simplified proof of the Parallel Repetition Theorem for certain games.
A recent result of Moshkovitz presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used there to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove the parallel repetition theorem.
We provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both l1 and l2 guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters is a good fortifier. We also show that using a fortifier (in particular l2 guarantees) is necessary for obtaining the robustness required for fortification.
This talk is based on a joint work with Ramprasad Saptharish, Girish Varma and Rakesh Venkat.
We prove that random n-by-n Toeplitz matrices over GF(2) have rigidity $\Omega(n^3/(r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves, for $r = o(n / \log n \log\log n)$, over the $\Omega( (n^2 / r) * \log(n/r) )$ bound that is known for many explicit matrices.
Our result implies that an explicit trilinear function f on n variables has complexity $\Omega(n^{3/5})$ in the multilinear circuit model suggested by Goldreich and Wigderson (ECCC, 2013), which yields an $\exp(n^{3/5})$ lower bound on the size of the so-called canonical depth-three circuits for f.
In [kal89], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in [KSS14], and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. This partially answers the question above posed in [KSS14], who asked if this result holds without the dependence on the individual degree. Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas). In this talk, we will give a brief survey of polynomial factorization and its relations to arithmetic complexity, and give an overview of the ideas used in the proof of our main result.