## Getting to the Roots of Factoring

* We revisit a paper from 1994 *

Richard Lipton is, among so many other things, a newlywed. He and Kathryn Farley were married on June 4th in Atlanta. The wedding was attended by family and friends including many faculty from Georgia Tech, some from around the country, and even one of Dick’s former students coming from Greece. Their engagement was noted here last St. Patrick’s Day, and Kathryn was previously mentioned in a relevantly-titled post on cryptography.

Today we congratulate him and Kathryn, and as part of our tribute, revisit a paper of his on factoring from 1994.

Read more…

## Theory In The Time of Big Data

* What is the role of theory today? *

Anna Gilbert and Atri Rudra are top theorists who are well known for their work in unraveling secrets of computation. They are experts on anything to do with coding theory—see this for a book draft by Atri with Venkatesan Guruswami and Madhu Sudan called *Essential Coding Theory*. They also do great theory research involving not only linear algebra but also much non-linear algebra of continuous functions and approximative numerical methods.

Today we want to focus on a recent piece of research they have done that is different from their usual work: It contains no proofs, no conjectures, nor even any mathematical symbols.

Read more…

## Polynomial Prestidigitation

* How some longstanding open problems were made to disappear *

Ernie Croot, Vsevolod Lev, and Péter Pach (CLP) found a new application of polynomials last month. They proved that every set of size at least has three distinct elements such that . Jordan Ellenberg and Dion Gijswijt extended this to for prime powers . Previous bounds had the form at best. Our friend Gil Kalai and others observed impacts on other mathematical problems including conjectures about sizes of sunflowers.

Today we congratulate them—Croot is a colleague of Dick’s in Mathematics at Georgia Tech—and wonder what the breakthroughs involving polynomials might mean for complexity theory.

Read more…

## Progress On Modular Computation

* New results on computing with modular gates *

Shiteng Chen and Periklis Papakonstaninou have just written an interesting paper on modular computation. Its title, “Depth Reduction for Composites,” means converting a depth-, size- circuit into a depth-2 circuit that is not too much larger in terms of as well as .

Today Ken and I wish to talk about their paper on the power of modular computation.

Read more…

## Making Public Information Secret

* A way to recover and enforce privacy *

McNealy bio source |

Scott McNealy, when he was the CEO of Sun Microsystems, famously said nearly 15 years ago, “You have zero privacy anyway. Get over it.”

Today I want to talk about how to enforce privacy by changing what we mean by “privacy.”

Read more…

## Coins on a Chessboard III

* From knight’s tours to complexity *

Von Warnsdorf’s Rule source |

Christian von Warnsdorf did more and less than solve the Knight’s Tour puzzle. In 1823 he published a short book whose title translates to, *The Leaping Knight’s Simplest and Most General Solution*. The ‘more’ is that his simple algorithm works for boards of any size. The ‘less’ is that its correctness remains yet unproven even for square boards.

Today we consider ways for chess pieces to tour not 64 but up to configurations on a chessboard.

Read more…

## Theory Meets Material Science

* A great presentation on thermoelectrics *

Akram Boukai is a researcher in material science, and an expert on converting heat to electric energy: thermoelectrics.

Today I wish to talk about a beautiful presentation he just gave at TTI/Vanguard in San Francisco.

Read more…