Skip to content

The Power Of ACC

March 20, 2014

Euler’s back-door pass to Gauss sinks a bucket


ACC stands for the Atlantic Coast Conference, which is an athletic organization that contains Georgia Tech and fourteen other colleges. In basketball, the top several teams in the ACC qualified for the NCAA championship tournament, which started today. We call the NCAA tournament “March Madness” because the opening rounds have games being shown on national TV seemingly every hour of every day, and often some spectacular upsets happen. Indeed Harvard has just beaten a favored University of Cincinnati team.

Today I want talk about another ACC: our own complexity class. Read more…

Happy St. Patrick’s Day 2014

March 17, 2014

A shocking story from our friendly Leprechaun


Neil L. is not a computer scientist—he is a Leprechaun. He has visited me every year since I started writing GLL, always visiting on St. Patrick’s day.

Today I want to report on what happened this year.
Read more…

Could We Have Felt Evidence For SDP ≠ P?

March 15, 2014

Evaluating mathematical beliefs

Rutgers in memoriam source.

Leonid Khachiyan in 1979 caused arguably the most sudden surprise to the West’s popular scientific understanding since the successful launch of Sputnik in 1957. His ellipsoid method gave the first algorithm for linear programming whose polynomial running time was verified. Thanks largely to Narendra Karmarkar it has been superseded by faster interior-point methods, while older algorithms have since been noted to run in polynomial time, but the breakthrough and inspiration came from Khachiyan. Could something like it happen again?

Today Ken and I want to ask whether recent argument over beliefs about {\mathsf{P=NP}}? can be evaluated in light of this shock.
Read more…

How To Carry Fame

March 10, 2014

Long proofs are not always the most important results


Michael Rabin is visiting Georgia Tech today and tomorrow to give a pair of distinguished lectures. Both of these will be on applications of cryptography. One is to help auctions avoid cheaters, while the other is to help elections avoid cheaters. I see a pattern. Ken sees another pattern— he is helping chess tournaments avoid cheaters.

Today I want to comment about Rabin’s fame and what makes a result important.

Read more…

Codes Meet Numbers

March 9, 2014

Results and problems about primes that make us think of coding theory

Cropped from source.

Zhi-Wei Sun is a professor in Mathematics at Nanjing University in China. He is the Editor in Chief of the recently-founded Journal of Combinatorics and Number Theory. His homepage is unique in prominently featuring a long list of

  • …not his awards,
  • …not his papers,
  • …not his theorems,
  • …but rather his conjectures.

Indeed we count 432 total conjectures in his list, subtracting one that he seems last year to have proved. They do not seem to be easy conjectures—this one implies the Riemann Hypothesis in a nontrivial way. Some of them involve powers of 2, which lend them a coding-theory flavor.

Today Ken and I wish to share ideas of using coding theory to prove number-theoretic results. Read more…

Can Plants Do Arithmetic?

March 3, 2014

The computational power of plants


Martin Howard and Alison Smith are research scientists at the John Innes Centre (JIC) in Norwich, England. JIC was founded as a horticultural institution by the philanthropist John Innes in 1910, and is today one of several independent institutes affiliated to the University of East Anglia. Howard and Smith are the senior scientists on a paper that claims to show that plants can perform arithmetic division. Their co-authors are Antonio Scialdone, Sam Mugford, Doreen Feike, Alastair Skeffington, Philippa Borrill, and Alexander Graf.

Today I thought we might look at their claim and see if theory can shed any light on it.
Read more…

Practically P=NP?

February 28, 2014

Solving is believing

Cropped from source.

Boris Konev and Alexei Lisitsa are both researchers at the University of Liverpool, who work in Logic and Computation. They have recently made important progress on the Erdős Discrepancy Problem using computer tools from logic. Unlike the approach of a PolyMath project on the problem, their proof comes from a single program that ran for just over 6 hours, a program administered only by them, but mostly not written by them.

Today Ken and I wish to talk about their paper and two consequences of it. Read more…


Get every new post delivered to your Inbox.

Join 1,244 other followers