Posted by: Alan Guo | July 21, 2011

## Complexity Classes: P, NP, co-NP, PSPACE

One of the seven Millennium Prize Problems stated by the Clay Mathematics Institute is the P vs. NP problem, which asks: is P = NP? What are P and NP exactly? In this post, I’ll go over some basic computational complexity classes: P, NP, co-NP, PSPACE, and known relationships between them, as well as intuition behind each class, without getting too technical. After reading, you should understand what the P vs. NP problem and you should get an idea of how the basic complexity classes are interrelated.

Posted by: Alan Guo | July 13, 2011

## Nuking mosquitoes: Commutative algebra and the Frobenius problem

This is one of those things that convinced me that commutative algebra was cool and actually useful for solving combinatorial problems. The Frobenius problem (commonly known as the coin problem, of which a special case is the McNugget problem) asks: given positive integers $a_1, a_2, \ldots, a_n$ with $\gcd(a_1, a_2,\ldots,a_n) = 1$, what is the largest integer $m$ that cannot be written in the form $m = c_1a_1 + c_2a_2 + \cdots c_na_n$ for nonnegative integers $c_i$? For demonstrative purposes, I’ll show you how you can use commutative algebra to solve the case $n = 2$, but the principle generalizes to larger $n$. At the end, I’ll speculate on how one might use this to solve higher-dimensional versions of the Frobenius problem, whatever that might mean.

Posted by: Alan Guo | July 12, 2011

## Cantor’s diagonal argument and undecidability

Probably every mathematician is familiar with Cantor’s diagonal argument for proving that there are uncountably many real numbers, but less well-known is the proof of the existence of an undecidable problem in computer science, which also uses Cantor’s diagonal argument. I thought it was really cool when I first learned it last year.

Posted by: Alan Guo | July 12, 2011

## New Character Unlocked: Alan

Hi everyone! I’m Alan, and I hope to contribute posts on connections between math and computer science. I majored in math and minored in CS as an undergrad, and will be a first year grad student in the computer science department at MIT in the fall. My interests on the math side include combinatorics, combinatorial games, and commutative algebra. On the computer science side, I’m interested in algorithms, complexity theory, quantum computing, and artificial intelligence. The underlying theme behind my interests is the application of mathematical knowledge to do things more efficiently or prove that they’re hard to do, and as such my posts will have particular emphasis on this theme.

My underdeveloped academic homepage can be found here.

In my spare time, I devoutly follow hedonism by enjoying food, music, movies and video games.

Posted by: JBL | July 9, 2011

## PSA: “RandomTableau” on Mathematica is broken (but Sage works fine)

This post is just a public service announcement: the function RandomTableau[p] in Mathematica is meant to give a random standard Young tableau of shape p. Though the documentation isn’t actually so helpful as to tell you explicitly what probability distribution it is allegedly generating, the only natural option is uniform over all tableaux of that shape. However, the function RandomTableau[p] does not generate tableaux uniformly. The rest of this post quickly outlines the evidence for this claim.

Posted by: Steven Sam | June 29, 2011

## Do the rank k matrices form an affine variety?

This question on math.stackexchange caught my eye and I thought I would reproduce the nice argument given by David Speyer, possibly with more background explained.

The question is as follows: is the variety of $n \times n$ matrices of rank exactly k an affine variety?

Those of rank at most k is an affine variety since they are defined by the vanishing of all minors of size k. This also shows that the rank k matrices form a quasi-affine variety. In fact, those of rank exactly n form an affine variety since this is the solution set of the equation $\det(x_{ij}) t = 1$ where t is a newly introduced indeterminant. However, this argument doesn’t work for smaller values of k, and we will see they cannot be written as the solution set of a system of equations, regardless of how many new indeterminants are introduced.

Posted by: yanzhang | June 15, 2011

## FPSAC 2011

I don’t really have internet these days, having made sure to keep my laptop at home so I can really take in the scenery (and the math, of course) at FPSAC 2011 in Reykjavik, Iceland. The country is gorgeous and some talks have been great. If you’re also around, feel free to come say hi!

-Yan (and Joel)

Posted by: JBL | May 20, 2011

## Origami and math

I’ve given a number of talks/run a number of events recently about origami and mathematics (at the MIT Pure Math Grad Student Seminar, as part of the MIT 150 Open House, at the MIT Museum for the Cambridge Science Festival, and at Burke HS in Dorchester). This is not directly related to my research at all, but it’s a pleasant hobby that produces some pretty results, both in terms of mathematics and origami.

The connection I like the most is related to origami as an axiomatic system. We follow the Greek notion that we should ask the question, “Using certain simple geometrical tools, what sorts of constructions can we make?” but replace the prefered tools of compass and straightedge by origami. In other words, imagine not that the infinite plane of Euclid is a piece of paper that we draw on but instead that it is a piece of paper that we fold. In this setting, certain constructions are very easy: for example, given two points, we can construct the (unique) perpendicular bisector of the segment joining them simply by folding one point onto the other. Similarly, it’s easy to construct the (unique) fold that passes through two given points. Read More…

Posted by: JBL | May 1, 2011

## Strogatz @ MIT

Two weeks ago, Steven Strogatz  gave a series of three lectures as part of the Simons Lecture Series.  (The pure math half of the series was given last week by Manjul Bhargava.)

The first lecture focused on coupled oscillators as a self-organizing system.  My favorite example of this phenomenon relates to the behavior of Hungarian audiences: at the end of (for example) an opera in Budapest, the audience members initially begin applauding as in the US, each beginning with his or her own frequency and phase.  However, after a moment or two, the entire audience synchronizes on a common frequency and phase.  This remarkable phenomenon happens far more quickly than would be possible if everyone had to get together and agree on a common frequency; instead, it’s the result of everyone subtly (and subconciously) adjusting their own rate and phase in response to the collective responses of the rest of the audience.  It turns out that with some reasonable assumptions and simplifications (e.g., involving mean field theory — I link that article partly in the hope that someone will improve it) one can write down and solve a system of differential equations that model this situation, and this allows one to say a lot about the overall behavior.  In particular, given a distribution of natural individual frequencies, there is some value for sensitivity to the behavior to others below which synchronization does not occur, followed by an abrupt phase-change at the critical value. Read More…

Posted by: JBL | March 31, 2011

## Intro post: JBL

Yan asked me to write an introductory post, and this is it; it takes the form of a sequence of factual statements.  I’m a classmate of Yan and Steven, and a former classmate of Sam and Alex.  I study combinatorics, mostly of the enumerative variety.  My first attempt to write this entry began “Intro poset.”  I have a webpage.  I have actually already written one post on this blog.  I don’t know what sorts of other posts I will write here, but they will probably relate to combinatorics.  The first and last sentences of this post are self-referential.