Skip to content

Lifting The Edge

May 17, 2014

A simple but powerful lemma: LTE


Preda Mihăilescu is a mathematician who solved a famous open problem. He was trained by some of the best mathematicians in the world, but spent his early career working on turbines and later on computer security. Yet he found time to solve a problem that had been open for over a century. Now he is a professor at Georg-August University in Göttingen.

Today Ken and I want to talk about solving hard open problems.
Read more…

NEXP and the Next Generation

May 13, 2014

Saluting Alan Selman upon the occasion of his retirement

Photos by Marty Kerker

Alan Selman is retiring after a long and illustrious career, the longest part spent alongside me in Buffalo. He arrived in August 1990, a year after me, and was hired as Chair. I was pleased to enact one of his first departmental decrees: “TGIF” parties. Before coming to Buffalo I’d experienced collegial gatherings with refreshments at Princeton, Oxford, and Cornell. So I happily volunteered to buy provisions every Friday morning at one of two gigantic grocery stores near the University, and lay out food and drink from 3:30 to 5. We kept it going for several years until it became unsustainable while the department’s growth made it impractical to squeeze everyone in to our one meeting room, in the building we had until two years ago.

Today Dick and I salute Alan’s technical and social contributions to Complexity Theory.
Read more…

The Easiest Impossible Problem

May 7, 2014

A simple problem that seems impossible to solve

Article source

Péter Frankl is a “Hungarian mathematician and street performer”—quoting our friends at Wikipedia. He is also a globetrotter, noting on his personal blog that he has visited over 100 countries. He resides in Japan, where he regularly appears on television to blend mathematics and entertainment for children. He visited Atlanta last July but I did not meet him—he worked with his friend Vojtěch Rödl over at Emory University which is across town. His specialty is extremal combinatorics, which is the study of how large or small a mathematical structure can be and still satisfy certain constraints.

Today I wish to talk about an approach to his famous conjecture.
Read more…

Does Program Size Matter?

May 3, 2014

A problem about this forgotten complexity measure


Erik Winfree is one of the leaders in DNA computation, especially the theory of self-assembly using DNA. He won a MacArthur Fellowship in 2000, among many other awards for his terrific work. With Paul Rothemund he wrote a STOC 2000 paper titled “The Program-Size Complexity of Self-Assembled Squares,” work that contributed to their sharing the 2006 Richard Feynman Prize in Nanotechnology.

Today Ken and I want to talk about program size: about how many instructions are needed to compute something. Read more…

Bell’s Fifty Year Old Mistake

April 30, 2014

My Missed Chance For Fame: The 1964 New York World Fair


Robert Moses was known as New York’s “Master Builder.” He was hired to run the 1964 New York Fair, for many reasons: he knew how to raise money, knew how to create huge infrastructure projects, he knew how to think big. He also knew how to fail. Unfortunately the fair failed to get the 70 million projected visitors and was considered a failure.

Today I want to talk about my recollection of the New York World’s Fair of 1964, failure or not.
Read more…

Galactic Sorting Networks

April 24, 2014

An improved sorting network to appear at STOC 2014

Teaching page source

Michael Goodrich is a Chancellor’s Professor at the University of California at Irvine, and recently served a year as Chair of the UCI Computer Science Department. He has designed algorithms that cover all of the area spanned by axes of cleverness and high performance. This includes attention to algorithms that we have called (clever but) galactic for having enormous constant factors and/or high exponents that forestall practical implementation. An example is his paper last year with his colleague Pawel Pszona, “Cole’s Parametric Search Technique Made Practical,” which greatly tunes up an algorithm-improvement technique of Richard Cole. Now he has a new paper taking a notorious behemoth head-on.

Today Ken and I wish to talk about Michael’s recent work improving on the size of the famous AKS sorting network. Read more…

In Praise Of P=NP Proofs

April 19, 2014

Why they can be important

Advertising source

Joe Bloggs is not a computer scientist, at least not one that we know. As noted by Wikipedia, Joe Bloggs is a “placeholder name” like “John Doe” or “Jane Roe” in the US, or “Ashok Kumar” in India. Sometimes real people have or acquire the placeholder names: Ashok Kumar (born Kumudlal Ganguly) was a famous actor in India, whose acting brothers also took the surname “Kumar,” and the “Roe” in Roe v. Wade is Norma McCorvey. We especially like the fact that “Joe Bloggs” came about long before there were blogs. A public restraining order is indeed called an “Ashok Kumar order” in India the way it is called a “John Doe order” in the US.

Today Ken and I consider whether there should be a “John Doe order” against submitting claimed proofs of {\mathsf{P = NP}} or {\mathsf{P \neq NP}}, and instead point out some reasons that we should look at such attempts by Ashok, Jane, or Joe.
Read more…


Get every new post delivered to your Inbox.

Join 1,537 other followers