When Less Is More
Claiming less may be a good idea
Robert Browning was an English poet of world renown in the Victorian age. His fame rests mostly on his dramatic monologues, in which characters reveal indirectly much about themselves. Here you can actually listen to a recording made in 1889 of him trying to read from his poem “How They Brought the Good News from Ghent to Aix,” which was one of Ken’s father’s favorites. After Browning’s passing on 12/12 of that year, this was said to have been the first recording preserving the voice of a deceased person.
Today I want to talk about claims of proofs that would resolve the 
Mounting or Solving Open Problems
Programs not programs
|
| src |
Richard Hamilton is the mathematician who laid out the route that eventually led to the positive solution to the three-dimensional Poincaré Conjecture by Grigori Perelman. He is the Davies Professor of Mathematics at Columbia University. While Perelman famously declined both the Fields Medal in 2006 and the official Clay Millennium Prize recognition in 2010, citing among other factors the lack of concomitant recognition for Hamilton, Hamilton was awarded the Leroy Steele prize in 2009, shared the Shaw Prize in 2011, and had earlier won the 2003 Clay Research Award alongside Terence Tao.
Today Ken and I wish to talk about programs in mathematics, not C++ programs, but programs of attack on a hard open problem. Ken likes the British form “programme” for this. Read more…
The Amazing Zeta Code
But can it encode itself?
|
| src |
Sergei Voronin was an expert in analytic number theory, especially the Riemann zeta function. He proved a sense in which the Riemann Hypothesis “ain’t necessarily so.” That is, he showed that certain complex analytic functions 
Today Ken and I wish to discuss an older result of his—proved in 1975—about the Riemann zeta function that seems to be amazing.
Barriers to P=NP Proofs
Why TSP resists being mapped to a small linear program
Sebastian Pokutta just gave a beautiful colloquium talk on proving lower bounds on the size of linear programs. He is a recent addition to the Georgia Tech faculty, but alas not in our College of Computing. He is a faculty member of the ISyE Department at Tech, which is perhaps the best industrial engineering department in the world, and his addition certainly adds to their strength.
Today Ken and I want to talk about results that he presented and their connection to attempts to prove that the Traveling Salesman Problem (TSP) can be solved in polynomial time.
Thanks For Sharing
An exchange of expertise and gifts
|
| src |
William Bradford was the first civic authority to proclaim a day of Thanksgiving in North America. He became governor of the fledgeling Plymouth Colony in 1621, a month after the settlers made a mutual-aid treaty with Massasoit, chief of the Pokanoket tribe. The Native Americans and settlers shared farming and hunting practices and technology, and provided for each others’ defense. With half of the settlers having already perished of disease, cold, and starvation the first winter, the colony would not have survived without this help.
Today we wish to talk about sharing and gifts between fields. It may not be life-and-death, but at least it’s our life.
A Wonderful Riff On Rank
The approximate rank of matrices—a great idea
Santosh Vempala is one of the world experts on high-dimensional geometry, and has made many beautiful contributions to this and other parts of theory. We have presented some of his results and open problems concerning high dimension geometry before. Many intuitions we have, not Santosh, from geometry in two and three dimensions fail in high dimensions. For example, the ratio of the corner-to-corner diameter to the volume of the 
Today I want to talk about a great new paper from Santosh that is joint work with Noga Alon.
Progress On Progressive Algorithms
Another attempt to capture the notion of progressive and a wrong proof of mine
Gary Miller is one of the great theorists. Starting with his award winning PhD thesis on a connection of the Riemann Hypothesis with primality testing, to his later work on graph separators, to his more recent work on practical methods for solving special linear systems in almost linear time, he has always done world class research.
Today I want revisit a idea that Ken and I have talked about before—the notion we called progressive algorithms. Read more…
The Ryan Williams Combine
Structuring his famous proof to build more on it
Ryan Williams is a deep theorist who is known among other things for his frontier-setting lower bounds against 
Today we make a “combine” out of Ryan’s famous
The Power Of Guessing
Some results and ideas on guessing and nondeterminism
David Doty and Michael Wehar are theorists who work in different areas of computational complexity, and are at different stages of their careers. Doty is at the California Institute of Technology as a fellow in the DNA and Natural Algorithms Group, while Wehar just finished his BS and MS from Carnegie Mellon University at age nineteen. Doty is one of the experts on self-assembly systems, while Wehar is focused—at least for now—on complexity theory: his honors thesis is titled “Intersection Emptiness for Finite Automata.”
Today Ken and I wish to discuss the power of guessing, the power of nondeterminism, and what we might learn about the question 
The Election Outcome
We predict that one of three outcomes will happen
|
| src |
Nate Silver is arguably the world’s foremost psephologist. This sounds like someone who foretells a person’s future by feeling the bumps on the head, but it is not—that’s a phrenologist. Psephology comes from the Greek psephos meaning “pebble,” which the Greeks used as ballots. It is the branch of political science that deals with the study and scientific analysis of elections.
Today Ken and I want to make a prediction about the election. We predict Nate Silver will be 0.95-correct with probability 0.95.
