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.
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.