Skip to content

STOC 1500

May 23, 2014


What STOC might have been like in old times

YoungCopernicus
src

Mikolaj Kopernik was a student of the professor mathematum Domenico Novara in 1500. They traveled from Bologna to Rome where Novara gave lectures on mathematics. We imagine that Novara might also have been asked to organize a symposium there on the practice of mathematics with mechanical aids, including the classical ruler-and-compass, abaci, astrolabes, and similar devices. Since the words “theory” and “theoretical” with their modern meanings trace only to the late 1500s, we suppose it might have been called the Symposium on Theology of Calculation (STOC).

Today Dick and I consider how STOC 1500 might have been similar to STOC 2014, which starts at the end of next week.
Read more…

Lifting The Edge

May 17, 2014


A simple but powerful lemma: LTE

220px-Preda_Mihailescu_vor_Tafel

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

AlanRet
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

PeterFranklPins
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

ErikHead_no4

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

Unknown

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

goodrich-equations-tiny
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…

Follow

Get every new post delivered to your Inbox.

Join 1,566 other followers