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.

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.

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 ${A \subseteq U = \mathbb{Z}_4^n}$ of size at least ${|U|^{1-\epsilon}}$ has three distinct elements ${a,b,c}$ such that ${2b = a + c}$. Jordan Ellenberg and Dion Gijswijt extended this to ${\mathbb{F}_q^n}$ for prime powers ${q}$. Previous bounds had the form ${|U| n^{-c}}$ 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.

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-${d}$, size-${s}$ ${\mathsf{ACC^0}}$ circuit into a depth-2 circuit that is not too much larger in terms of ${d}$ as well as ${s}$.

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

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.”

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 ${n \times n}$ boards.

Today we consider ways for chess pieces to tour not 64 but up to ${2^{64}}$ configurations on a chessboard.