My Name

My given name, Yuval, is biblical, and even mentioned in Paradise Lost (lines 558^b–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.

My Nature

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.

Contact Info

My email is yuvalf﹫cs.toronto.edu.

My office is SF 4302C. It used to be SF 4301B.

Official papers

• 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 √ n  !). 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.
• Triangle-intersecting families on eight vertices, on arXiv. An "algebric" 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.
• Exponential lower bounds for AC⁰-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). 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.
• Space Complexity in Polynomial Calculus, with Massimo Lauria, Jakob Nordström, Neil Thapen and Noga Zewi, CCC 2012. 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, with Justin Ward. 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 analysis makes a surprising use of Padé approximants to e^x evaluated at the point x=c.

Work in progress

• Universal Codings of Integers, in progress. 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.

TSS Lectures

• 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 AC⁰, 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.

Expositions too long for a TSS

• Smolensky's polynomial method without Gröbner bases. An exposition of Smolensky's 1993 paper, showing how to use the algebraic method to obtain AC₀ correlation bounds on parity and majority. You'll have to read about the Razborov-Smolensky polynomial approximations of AC₀ 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

• Lagrange's proof of the four square theorem (in French). English translation.
• Lagrange's proof of Wilson's theorem (in French).

Papers on the transcendence of e

• Hurwitz's proof (in German). Herstein's translation (from his book Topics in Algebra).
• Gordan's proof (in German).
• Hilbert's proof (in German).

Other papers

• Hurwitz's proof that four-square-like identities only occur in 1,2,4,8 dimensions (in German). I really liked this one, so I wrote it up in English.
• McKay's easy proof of Cauchy's group theorem (existence of an element of order p for any prime divisor of a group's order).

Other Math Stuff

• 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 L₁ 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 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.
• 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.
• Restricted 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.
• Equivalent 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.

Alternative Proofs

• Proof of the weighted version of EKR using Katona's circle method (sketch). We show how to prove that the μ_p version of EKR using Katona's circle method, including uniqueness.
• Two proofs of a fact about relatively prime numbers. We prove that (x,y)=1 implies (x+y,xy)=1 using the GCD proof system. There's also a generalization to more than two variables.
• Combinatorial interpretation for a geomtric series identity. The product of 1/(1−x) and 1/(1−y) is another geometric series, 1/(1−x−y+xy). We show how to interpret this combinatorially.
• Thirteenth proof of a result about tiling a rectangle. A paraphrase of the 13th proof from Stan Wagon's well-known Fourteen proofs of a result about tiling a rectangle.
• A positive proof of Dehn's theorem. We prove Dehn's theorem stating that if a rectangle can be covered by rational rectangles (those whose sides are rational multiples of one another), then it must be rational. The proof is along the lines of Dehn's original proof, which I implicitly assume that you already know (sorry). The original proof uses a Q-homomorphism that changes all coordinates, such that some of the side lengths become negative. This is deemed unintuitive, and our proof fixes the argument so that all side lengths remain positive.
• Wilkie's non-standard proof of a switching lemma, translated from Wilkie's lecture notes in French. See also Woods' paper Approximating the structures accepted by a constant depth circuit or satisfying a sentence — a nonstandard approach.

Math Riddles

• 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 2ⁿ 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.
• Range 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).

Theses

• MSc thesis. Slightly better analysis of an algorithm approximating bandwidth on trees. Slides.

Other Stuff

• A collection of poems by Shalom Shabazi (in Hebrew).
• A poem by David Avidan (in English).
• Patience collection by Ella von Haunstein, early 20th century (in German), regrettably without the diagrams. Original title is 20 Patiencen, i.e. 20 Patience Games.
• Ceramics.
• What am I seeing in the background?
• An etiology of the major and minor scales.
• The Kuzari in Arabic.
• Some RoR grooves: simple and fancy. Generate them yourself using python. Cheat sheet.