My given name, Yuval, is biblical, and even mentioned in Paradise Lost (lines 558b–563).
Yuval was the Urmusikant (his volant touch instinct through all proportions low and high fled and pursued transverse the resonant fugue).
See also The Legend of Jubal.
My surname is a distortion of Feldmaus, field mouse.
I started my PhD studies at the University of Toronto (UofT) in 2009.
I'm in the department of computer science (DCS), theory group.
My advisor is Toni Pitassi.
I used to be the cookie monster.
My email is yuvalf﹫cs.toronto.edu.
My office is SF 4302C. It used to be SF 4301B.
I am graduating sometime in July 2013.
I will be attending the special semester on real analysis in computer science in the Simons institute, Berkeley.
After that I'm heading to the IAS in Princeton for three semesters.
My Research Statement and CV.
- Threshold models for competitive influence in social networks with Allan Borodin and Joel Oren, WINE 2010. We analyze several two-player models for influence maximization in social networks. Some of them present erratic behavior (one of them is even NP-hard to approximate to within
!). Another model is amenable to analysis, and we give a constant-factor approximation algorithm for one player against the other one.
- Triangle-intersecting families of graphs, with David Ellis and Ehud Friedgut, JEMS 14:3, 2012, 841–885. Presentation, another one. We show that a family of graphs, the intersection of any two of which always contains a triangle, can contain at most 1/8 of the graphs. Moreover, the only families achieving this bound consist of all supergraphs of a fixed triangle.
- Exponential lower bounds for AC0-Frege imply polynomial Frege lower bounds, ICALP 2011. Slides. It's an easy exercise to convert a (balanced) formula into a constant-depth circuit with only a subexponential blow-up. We show how to extend this to proofs. An old result of Reckhow implies that we can always assume that all formulas in the proof are balanced.
- Lower bounds for context-free grammars, IPL 111:18, 2011, 895–898 (slightly corrected version). Some exponential lower bounds on the size of context-free grammars for some languages, mostly finite. These include the language of all kth powers, and the language where the number of occurrences of every symbol must belong to some given finite set. The method is an extension of the proof of Theorem 30 in the interesting paper Regular Expressions: New Results and Open Problems by Ellul, Krawetz, Shallit and Wang (although it was discovered independently). The paper is a summary of several of my answers on math.stackexchange. Earlier version can be found under other math stuff.
- Maximum Coverage over a Matroid, with Justin Ward, STACS 2012. Slides (CTW'11), Other slides (STACS'12). An optimal approximation algorithm for maximum coverage over a matroid, using non-oblivious local search.
- Automatic web-scale information extraction, with Philip Bohannon, Nilesh Daliv, Nori Jacoby, Sathiya Keerthi and Alok Kirpal, SIGMOD'12. We develop a system for semiautomatic feature extraction from websites. Our system tries to fit a schema into sample webpages harvested from a website, using a human for feedback.
- Space Complexity in Polynomial Calculus, with Massimo Lauria, Jakob Nordström, Neil Thapen and Noga Zewi, CCC 2012 (ECCC). Highlight: Linear space lower bound for PCR for a 4CNF version of the pigeonhole principle.
- A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint, FOCS 2012, with Justin Ward. Original FOCS version, version on ArXiv (these versions are radically different from the final version), extended version (this version contains extra material). We give a non-oblivious local search algorithm for the problem of maximizing a monotone submodular function subject to a matroid constraint. Our algorithm achieves the optimal approximation ratio 1−1/e. When the function has curvature c, we give an algorithm achieving the optimal approximation ratio (1−e−c)/c. The original analysis makes a surprising use of Padé approximants to ex evaluated at the point x=c, though this is avoided in the simplified version.
- The complexity of the comparator circuit value problem, with Stephen Cook and Dai Lê. We solve some earlier problems raised in an earlier paper by Stephen Cook, Dai Lê and Yuli Ye. The earlier paper, following previous work by Subramanian, defines a complexity class CC based on comparator circuits. We clarify the definition of CC by constructing universal circuits. We provide oracle separations between CC and NC. Finally, we explain a connection between the Gale-Shapley algorithm for stable marriage and Subramanian's fixed-point algorithm.
- Inequalities on submodular functions via term rewriting, IPL 113, 2013, 457–464. We devise a non-constructive method for proving inequalities in the contex of submodular functions. As applications, we find the locality ratio of local search in various setups.
- A quasi-stability result for dictatorships in Sn, with David Ellis and Ehud Friedgut, submitted. We prove that a Boolean function on Sn that is close to a linear combination of double cosets is in fact close to a union of double cosets. Our proof works when the support of the function is of the order of magnitude of a few double cosets.
- A stability result for balanced dictatorships in Sn, with David Ellis and Ehud Friedgut, submitted. We prove that a balanced Boolean function on Sn that is close to a linear combination of double cosets is in fact close to a dictator (a function determined by one coordinate).
- A quasi-stability result for low-degree Boolean functions on Sn, with David Ellis and Ehud Friedgut, preprint. We prove that a Boolean function on Sn that is close to a linear combination of k-double cosets is in fact close to a union of k-double cosets, assuming the support of the function is of the order of magnitude of a few k-double cosets.
- Towards an understanding of Polynomial Calculus: new separations and lower bounds, with Massimo Lauria, Mladen Mikša, Jakob Nordström and Marc Vinyals, ICALP 2013. Using a connection between the Atserias-Dalmau game and the Bonacina-Galesi framework, we show that Tseitin formulas on expander graphs with double edges can be refuted in PC in quasilinear size and constant degree, but require linear space even in PCR. Using the Bonacina-Galesi framework and some random graph theory, we show that Tseitin formulas on (simple) random regular graphs require Ω(n1/2) space to refute in PCR, asymptotically almost surely.
- Efficient vote elicitation under candidate uncertainty, with Craig Boutilier and Joel Oren, IJCAI 2013. We analyze the plurality and Borda voting procedures under several situations, trying to estimate how long a prefix from each voter's preference profile is needed to predict the outcome of the elections. In some cases (Mallows distribution), we can predict the outcome of the elections with high probability without ever looking at the votes!
- Average case lower bounds for monotone switching networks, with Toni Pitassi, Robert Robere and Steve Cook, submitted. We extend recent work by Potechin and Chan and Potechin on monotone switching networks to the setting of average case lower bounds. We prove exponential lower bounds on monotone switching networks for GEN having polynomially-small advantage (with respect to a specific natural distribution). Our lower bounds imply a strong separation of the monotone NC hierarchy and between monotone NC and monotone P. For example, we exhibit a problem in monotone P which cannot be solved in monotone NC even with only polynomially-small advantage.
Work in progress
- Universal Codes of the Natural Numbers, submitted. We consider the problem of uniquely decodable binary codes for the natural numbers, with non-decreasing codeword lengths. We show that the existence of a "scale" (cofinal well-ordered set) of codes is independent of ZFC. On the way, we describe constructions more general than the ones used by Elias to construct his alpha, beta, gamma, delta and omega codes.
- Spectral Methods for Intersection Problems, in preparation. We survey recent results by Friedgut and coauthors on the theme of intersecting families. The survey started its life as a depth paper.
- Monotone feasible interpolation as games. Slides for a talk at LCC 2011. We deconstruct old results by Bonet, Pitassi and Raz and by Krajíček and present them in terms of games.
- A separation between semantic and syntactic cutting planes, with Massimo Lauria. We engineer a form of the clique-coloring principle which is easy for semantic cutting planes but hard for syntactic cutting planes. As a bonus, we get two contradictory inequalities which require exponential size syntactic cutting planes refutations.
- Seven Trees in One , given on 16/09/2009.
My take on a wonderful
paper by Andreas Blass. A controversial TSS.
- Modern Integer Factorization Methods , given on 25/11/2009. In the words of Periklis, the worst TSS ever.
- Two Proofs of the Central Limit Theorem , given on 20/01/2010. One proof is via the cumulants, the other via the moments. As a bonus, we also prove the asymptotic normality of the number of (distinct) prime factors.
- Using polynomials to prove that PARITY is not in AC0, given on 13/09/2010. I presented two proofs, one using Smolensky's polynomials over finite fields, and the other using ABFR's polynomials over the integers.
- Exponential lower bound for bounded-depth proofs of the pigeonhole principle, given on 11/01/2010. I followed Urquhart and Fu's Simplified lower bounds for propositional proofs, skipping the switching lemma. I tried to run the proof "top-down" instead of "bottom-up".
- Hardness of approximating set cover, an exposition of Feige's celebrated result. Given on 23/01/2010 as part of the PCP reading group.
- Subramanian's stable matching algorithm. Perhaps will be given in the future. Subramanian's algorithm solves the stable matching problem using comparator circuits. We discuss a connection between the standard Gale-Shapley algorithm and Subramanian's algorithm, via an intermediate algorithm.
- Matrix multiplication, part 1, given on 02/02/2012. Normal form, tensor notation, border rank, Schönhage's asymptotic sum inequality, Coppersmith's fast rectangular matrix multiplication.
- Matrix multiplication, part 2, partially given on 09/02/2012. The laser method, Coppersmith-Winograd.
- Permanent is hard to compute even on a good day, given on 17/09/2012. Cai, Pavan and Sivakumar showed that it is hard to compute the permanent even with an inversely polynomial success probability (assuming the worst-case hardness of permanent). Their proof combines the LFKN protocol with list-decoding of Reed-Solomon codes (Sudan's algorithm).
- Submodular maximization, given on 31/01/2013. We survey several recent results on submodular maximization. We don't give details of proofs, but state the algorithms and sketch the proofs. We also discuss lower bounds and some open problems.
Expositions too long for a TSS
- Reformulation of the Alekhnovich-Razborov degree lower bound for the polynomial calculus, including the Galesi-Lauria adaptation to the graph ordering principle. Assumes you already know what the polynomial calculus is.
- Smolensky's polynomial method without Gröbner bases. An exposition of Smolensky's 1993 paper, showing how to use the algebraic method to obtain AC0 correlation bounds on parity and majority. You'll have to read about the Razborov-Smolensky polynomial approximations of AC0 somewhere else.
- Rechkow's theorem (in preparation). An exposition of part of Reckhow's 1976 thesis: how to transform a (Hilbert-style) Frege proof into a proof in which all formulas are balanced.
Golden Age Papers
Papers by Lagrange
Papers on the transcendence of e
Other Math Stuff
- List of all inequivalent non-trivial antichains on the Boolean lattice of dimension 6, apart from the empty antichain and the antichain consisting of the empty set. Alternatively, this is a list of all inequivalent non-constant monotone Boolean functions on six inputs, given by their minterms. If you're interested in smaller dimensions, ignore lines containing the larger digits. Related sequence: A003182 (which includes the two trivial cases).
- Triangle-intersecting families on eight vertices, on arXiv. An "algebraic" proof that a triangle-intersecting family contains at most 1/8 of the graphs, unfortunately working only for up to eight vertices. Some discussion on how I tried to extend it beyond that.
- Submodular functions and random k-subsets. Consider the problem of maximizing a (not necessarily monotone) submodular function under an exact cardinality constraint. How good is the trivial algorithm that just selects a random set? The answer is k(n−k)/n(n−1) (double if the function is symmetric).
- Khintchine-Kahane using Fourier Analysis. Latała and Oleszkiewicz proved the special L1 case of the Khintchine-Kahane inequality using Fourier analysis, but they failed to write it this way. We mend their ways.
- Regular languages closed under Kleene plus, writeup of an answer to a question on cstheory.stackexchange regarding regular languages closed under Kleene plus (the OP called them circular languages). We show that each such language is the union of languages of the form L+; the union cannot be assumed to be disjoint, and in some cases is inherently "ambiguous". We also give an exponential algorithm for deciding this property, and show that it is coNP-hard. See also the following item.
- Deciding whether a regular language is power-closed is PSPACE-complete. A regular language is power-closed if all powers of every word in the language also belong to the language. We show that given a DFA, it is PSPACE-hard to determine whether the language it generates is power-closed. For a simpler proof, see this answer on cstheory.
- Exponential lower bound (in terms of alphabet size) for context-free grammars describing the language where each symbol occurs an even number of times. Answer to a question on math.stackexchange. See also official paper above.
- Number of self-avoiding walks on the integers which move at most two integers at a time (in preparation), following a question. We enumerate the number of these walks of given length up to a polynomial.
- The Carromboard Problem (follow-up on EWD1211a). This note generalizes the carromboard problem, where you have a square table with switches in the center of each side, you cannot see their states but can press at most two of them at a time, after which you must close your eyes while the table is turned by someone else. Your goal is to get all switches in the same state (on or off). We generalize this to an arbitrary number of sides (we need more than two hands) and any Abelian group for the switches.
- Elfi's Problem. Consider the sequence n mod
x for x from 1 up to √n. Extract from it all local minima,
and graph them (with their x co-ordinates). If you scale down both axes
by square root of n, you'll get a funny zigzag graph. This note explains
why, with additional generalizations (minima of minima and so on).
- Largest adjacent segments on the unit
circle. Suppose n random points are thrown on the unit
circle (only the circumference). They create n random segments,
whose lengths we can order by size. There are nice expressions for their
expected ordered sizes. If we consider the lengths of two adjacent
segments (and again order them), we show how to explicitly calculate the
expectations. They turn out to be ugly, so there's probably no
corresponding simple expression.
permutations. Another proof of the well-known fact that 123- and
132-avoiding permutations are counted by the Catalan numbers. Simion and
Schmidt's classic paper (Restricted Permutations, European J. Combin. 6
(1985), 383–406) is a much better reference — highly recommended!
- Until cannot be expressed using next, always,
eventually. Proof of this well-known fact in LTL. Perhaps the same
as what can be found in the literature.
definitions of the Sprague-Grundy function. Answer to an exercise in
a course on combinatorial game theory. I liked the answer so much that I
delegated it to a separate file.
- NOT riddle: how many NOT gates are needed to
invert n inputs? This riddle is quite easy.
- Orthogonal matrices with optimal L2 norm: take an n×n orthogonal matrix, and consider its first k rows. The average squared L2 norm of a column is k/n. A question in The Probabilistic Method (chapter 2, question 8) asks for examples of equality. Hadamard matrices are the standard example when n is a power of 2; can you do it for arbitrary n?
- Riddle concerning ±1
vectors: you're given the list of all 2n vectors
of length n with ±1 entries. Someone erased some of
the entries to zero. Show that that there's a non-empty set of vectors
that add to the zero vector. This is my favorite riddle! It's not easy,
but has a very simple, surprising solution. Also on Mathoverflow.
of symmetric matrices mod 2: show that the diagonal of every symmetric matrix over
GF(2) is contained in its range. Not so easy, somewhat messy solution. Also on Mathematics (StackExchange).
- MSc thesis. Slightly better analysis of an algorithm approximating bandwidth on trees. Slides.