Who Needs Crossings?: Hardness of Plane Graph Rigidity
In The 32nd International Symposium on Computational Geometry, June 2016. Conference presentation of this paper.
Prime Portraits
In The 19th Annual Bridges Conference, Jyväskylä, Finland, pages 359–362, August 2016. Conference presentation of this paper.
Rubber band sculptures.
In The Tenth Gathering for Gardner, April 2012.
Folding equilateral plane graphs.
In The 22nd International Symposium on Algorithms and Computation, Yokohama, Japan, December 2011. Conference presentation of this paper.
A topologically convex vertex-ununfoldable polyhedron.
In The 23rd Canadian Conference on Computational Geometry, August 2011. Conference presentation of this paper.
Edge-unfolding orthogonal polyhedra is strongly NP-complete.
In The 23rd Canadian Conference on Computational Geometry, August 2011. Conference presentation of this paper.
Hinged dissections exist.
In The 24th Annual Symposium on Computational Geometry, June 2008. Conference presentation of this paper.
Permutation groups and the Schreier-Sims algorithm.
In Great Ideas in Computer Science. MIT, May 2013.
Mysteries of triangle geometry.
In The Pure Math Graduate Student Seminar. MIT, May 2013.
Abstract:
There is a common belief that elementary Euclidean geometry is boring for mathematicians because it is solvable by throwing automated algebraic geometry algorithms at brute-force coordinate calculations. While such algorithms certainly do exist (and are quite interesting themselves), nevertheless, there remains a unique sense of elegance, insight, and achievement in synthetic arguments that cut to the heart of a geometric configuration. More fundamentally, Euclidean geometry is brimming with results that seem so coincidental, so counterintuitive, that automated proofs do not detract from their mystique but instead *demand* a deeper moral understanding. In this talk we will (re)visit some incredible geometric facts concerning the humble Euclidean triangle, and we'll try to offer insight to some otherwise totally bizarre "coincidences."
Hypnotic stylings of Penrose tilings.
In The Simple Person's Applied Math Seminar. MIT, March 2013.
Abstract:
Structure in chaos, simplicity in complexity, and periodicity in—wait, nevermind, Penrose tilings are decidedly not periodic. That's the whole point! Originally studied in the 1970s as one of the simplest tiling rules that forces nonperiodic behavior (and arguably still holding that title), Roger Penrose's pair of rhombuses hold infinities of surprises, including mathematical, visual, physical, computational, and even hygenical. This talk surveys some of these tilings' most fascinating, unexpected, and beautiful properties discovered by de Bruijn, Conway, and others, and features an abundance of proofs, a surplus of food, and a profusion of pretty pictures.
Algorithms for Factoring (Multivariate) Polynomials
In The Seminar on Topics in Arithmetic, Geometry, Etc.. MIT, November 2012.
Abstract:
Showing PRIMES is in P with \(\mathbb{F}_p\).
In The Pure Math Graduate Student Seminar. MIT, October 2012.
Abstract:
Primality testing, i.e., determining whether a given integer is prime, remains an important and fundamental algorithmic task. Efficient randomized algorithms for primality testing (with vanishingly small error probability) have long been known, but a recent breakthrough by Agrawal, Kayal, and Saxena shows that randomness is unnecessary: they provide an efficient, deterministic algorithm to check primality. In this talk, we will discuss this deterministic algorithm, its analysis, and its beautiful underlying number theory.
Reconstructing polyhedra.
In The Simple Person's Applied Math Seminar. MIT, October 2012.
Abstract:
How little information is necessary to uniquely specify or reconstruct a polyhedron? For example, is it sufficient to know just the face normals and face areas? Is it sufficient to know only the intrinsic surface metric? Minkowski and Alexandrov say "yes" and "yes" respectively. This talk will present proofs of both results and extensions thereof.
Generating PIE.
In Undergraduate Mathematics Association. MIT, October 2012. Invited Putnam talk.
Abstract:
In this talk we will learn a simple recipe for PIE—the Principle of Inclusion-Exclusion—whose main ingredient is Generating Functions. Mix together one dash of theoretical derivation linking the topics, a generous handful of examples (preferably tough for proper consistency), a few leaves from your favorite labelled tree, and a pinch of humor (to taste). Let sit for an hour, and enjoy! This PIE recipe is sugar-free but hopefully still pretty sweet.
Proofs without words, without words.
In The Pure Math Graduate Student Seminar. MIT, April 2012.
Abstract:
…
Drawing with linkages.
In The Simple Person's Applied Math Seminar. MIT, April 2012.
Abstract:
A linkage is a (potentially complicated) mechanical system formed by joining rigid bars (line segments) at endpoints, some of which may be pinned in the plane. Choose one vertex and look at its locus as the linkage moves. What kinds of loci are possible? The answer may surprise you, and the proof of this theorem (and some extension) will draw on some nice constructions and ideas.
Laman graphs and generic rigidity.
In The Pure Math Graduate Student Seminar. MIT, November 2011.
Abstract:
An embedding of a graph in \(\mathbb{R}^n\) is flexible if there are edge-length preserving motions of the vertices other than the Euclidean motions; otherwise the embedding is rigid. We can extend this concept to combinatorial graphs by asking if a "generic" embedding in \(\mathbb{R}^n\) is flexible or rigid. These and similar concepts are central to a geometric branch of graph theory known as rigidity theory.
In the plane, the minimal generically rigid graphs are called Laman graphs, and they have many nice combinatorial characterizations, some of which we will see and prove in this talk. We will also discuss some geometric, linear-algebraic, and even Galois-theoretic properties of this rich family of graphs from a rigidity standpoint.
Wipe the floor with beatty sequences.
In Undergraduate Mathematics Association. MIT, November 2011. Invited Putnam talk.
Abstract:
For an irrational number \(r\), we define the associated Beatty sequence as \(B_r = (\lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor, \ldots)\). The celebrated Beatty's Theorem says that two positive irrationals \(r\) and \(s\) satisfy \(1/r + 1/s = 1\) if and only if \(B_r\) and \(B_s\) together contain each positive integer exactly once. Beatty sequences enjoy much structure even beyond this, and they are therefore often found lurking underneath the floorboards in Putnam problems. In this talk we will explore some of their properties and apply them to many challenging problems.
Origami is hard in theory, too.
In The Simple Person's Applied Math Seminar. MIT, October 2011.
In Harvard Math Table, September 2011, under the name Unfolding polyhedra is NP-hard.
Based on results from Edge-unfolding orthogonal polyhedra is strongly NP-complete and Folding equilateral plane graphs.
Abstract:
What do floors, cages, drains, pipes, wires, bricks, and towers have in common? They're all used in a fairly involved construction[1] showing that the problem of polyhedral Edge Unfolding—an important problem in Computational Origami—is computationally intractable. (The Edge Unfolding problem asks whether, for a given polyhedron, it is possible to unfold the surface into a non-overlapping net in the plane while keeping the faces intact.)
What if we try to make Origami simpler by recasting it in lower dimensions? Specifically, we could ask whether a given planar graph (with edge lengths) can be "folded flat" along a line without overlaps. It turns out that any attempts to solve this problem efficiently are also destined to fall flat.
In this talk we will offer background and motivation for these Computational Geometry problems and sketch (literally!) their hardness proofs.
[1] Sorry for building[2] up such a bad joke
[2] OK, maybe not that sorry
Flexible polyhedra and the bellows theorem.
In The Pure Math Graduate Student Seminar. MIT, March 2011.
Abstract:
Imagine the temperature is 40 degrees bel[l]ow zero, so you reach for a tool to b[el]low some air to fan the fire. Can this tool be ([l]low-tech as it may sound) made from a polyhedron? As will be el[l]ucidated in this talk, the answer is "yes, but no." On the "yes" side, there do exist polyhedra that are flexib[ell] o[w]r pliant, even with rigid, triangular faces. Some examples are easily constructib[ell], as we will see. Most surprisingly, however, even these flexing polyhedra we cannot label[l] as "bellows": the volume remains constant during the flex! Though you may doub[ell] o[w]ver in disbelief, in this talk we will discuss a complete proof due to Connelly, et al.
There are no prerequisites, except a love of Thai food (maybe with portobello[w]s?). Prepare to learn more about valuation rings than you ever thought would bel[l]o[w]ng in a talk on Euclidean geometry.
To those who read this far, I sincerely abellowgize.
Stably surrounding spheres with smallest string size.
In The Simple Person's Applied Math Seminar. MIT, March 2011.
In Harvard Math Table, November 2010.
Abstract:
\eps more.Summation by parts on the battlefield.
In Undergraduate Mathematics Association. MIT, November 2010. Invited Putnam talk. Based on material from this Olympiad training article.
Abstract:
Integration by parts provides a handy method to integrate a product \(f(x) \cdot g(x)\) by instead considering the integral of \(f'(x) \cdot G(x)\), where \(f'\) is the derivative of \(f\) and \(G\) is an antiderivative of \(g\). Its discrete analog, known as "Summation by Parts" or "Abel Summation"[1], deals instead with differences and partial sums, and it is a simple but unusually powerful weapon to have in your arsenal—especially, perhaps, when doing battle with some Putnam problems.
In this talk you will receive basic weapons training, learning how to use this innocuous-seeming hand grenade to blow some enemies (enemy sums?) into, well, parts. You will also learn to recognize when such a maneuver could be add-vantageous. Finally, we will apply this training in simulated combat against incomplete units of Egyption factions—er, fractions.
[1] Yes, it is really called "Abel Summation." I did not just name it after myself. Some Norwegian mathematician named it after me instead…
Thirteen ways of looking at a Nesbitt.
In Undergraduate Mathematics Association. MIT, October 2010. Invited talk.
Abstract:
Have you ever wanted to know more proofs of Nesbitt's Inequality than you ever wanted to know? No? Well, in this talk, we'll see how close we can get. Along the way we'll discuss what makes the proofs different (or not), ask where they may have come from, and thereby discover how we could have dreamt them up ourselves.
With apologies to Wallace Stevens.
Empirical knot theory.
In Harvard Math Table, April 2010.
In The Simple Person's Applied Math Seminar. MIT, October 2010.
Abstract:
Abstract: Learn to create art with rubber bands, and then explore the knot-theoretic limitations of the medium. More specifically, consider the problem of recreating a given graph out of rubber bands, where each edge corresponds to (the two strands of) a single rubber band and each node non-trivially joins all incoming edges. Which graphs are realizable in this way, given that the rubber bands are originally unlinked?
After a few minutes playing with rubber bands, we will provide a complete mathematical answer to the above question, and obtain as a corollary a versatile construction (and verification) for Brunnian links.
Gröbner bases and universal Gröbner bases.
In The Pure Math Graduate Student Seminar. MIT, September 2010.
Abstract:
Gröbner Bases are invaluable tools for computing with polynomial ideals, providing simple algorithms to test for ideal membership and equality; to compute elimination ideals, projective closures, radicals, syzygies and free resolutions; and much, much more.
A Gröbner basis for a polynomial ideal depends strongly on a given monomial ordering, which is used to single out a polynomial's "leading" monomial. Different monomial orderings often lead to drastically different Gröbner bases for the same ideal, and as there are uncountably many different monomial orderings, we may expect that there could be many inequivalent Gröbner bases. Surprisingly, this intuition is false: there exists a single Gröbner Basis, called a Universal Gröbner Basis, that is good for all monomial orderings simultaneously!
The first part of the talk develops basic properties of Gröbner Bases as well as an algorithm to compute them. In the second part, we give a fun, topological proof for the existence of a Universal Gröbner Basis.
What is the LLL algorithm?
In Harvard Math Table, October 2009.
The rap battle of the Millenium.
In Harvard Math Table, May 2009.
Abstract:
One night, two bards, and seven very, very hard problems. \(\mathbb{QED}\).
Hinged dissections exist.
In Harvard Math Table, November 2008. Received the Robert Fletcher Rogers prize for the best Harvard Math Table talk by an undergraduate during the 2008 academic year. An informal talk about this paper of the same name.
How many primes?
In Harvard Math Table, February 2007.
Abstract:
\(p\) proofs of the infinitude of the prime numbers (where \(p\) may or may not itself be prime)
Mean geometry.
In W.K. McNabb Mathematics Contest Awards Banquet, 2005. Invited talk.