Skip to content

Getting to the Roots of Factoring

June 29, 2016


We revisit a paper from 1994

RichardRelaxed2

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

June 18, 2016


What is the role of theory today?

AnnaAtri

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

June 15, 2016


How some longstanding open problems were made to disappear

CrootLevPach

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.
Read more…

Progress On Modular Computation

May 28, 2016


New results on computing with modular gates

ChenPapakonstantinou

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.
Read more…

Making Public Information Secret

May 20, 2016


A way to recover and enforce privacy

ScottMcNealyHighNoon
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

May 14, 2016


From knight’s tours to complexity

Warnsdorff3
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.
Read more…

Theory Meets Material Science

May 9, 2016


A great presentation on thermoelectrics

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

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