Skip to content

Limits On Matrix Multiplication

August 30, 2018

Can 2.3728639 be best?

Personal site; note puzzles

Josh Alman is a graduate student at a technical school in the Boston area. He is working on matrix multiplication, among other problems in complexity theory, and is advised by Ryan Williams and Virginia Vassilevska Williams.

Today we comment on his recent paper with Virginia on the limits of approaches to matrix multiplication.
Read more…


Do You Want to Know a Secret?

August 25, 2018

A riff on writing style and rating systems

Cropped from source

Mark Glickman is a statistician at Harvard University. With Jason Brown of Dalhousie University and Ryan Song also of Harvard—we’ll call them GBS—he has used musical stylometry to resolve questions about which Beatle wrote which parts of which songs. He is also a nonpareil designer of rating systems for chess and other games and sports.

Today we discuss wider issues and challenges arising from this kind of work.
Read more…

Power Circuits

August 18, 2018

Not anything to do with electrical engineering

Alexei Miasnikov, Alexander Ushakov, and Dong Wook Won are the authors of a brilliant paper, “Power Circuits, Exponential Algebra, and Time Complexity.” It and several followup papers give polynomial-time algorithms for problems in group theory where only highly exponential algorithms were previously known. The algorithms use a new scheme for manipulating highly succinct representations of certain huge integers. Regarding this, the first followup paper says:

In this sense our paper is more about compression and data structures than about algorithmic group theory.

Today Ken and I want to discuss the compression method called power circuits.
Read more…

Winner Of 2018 Knuth Prize Is:

August 16, 2018

A great choice

Cropped from 2016 KTH grant news source

Johan Håstad is the winner of the 2018 Donald E. Knuth Prize. We were going to keep you in suspense, but one of our “blog invariants” is to lead with the name(s) of those who are featured. He is very well deserving. And he has proved many wonderful theorems.

Today the entire GLL editorial staff would like to thank the committee for their great selection.
Read more…

Desperately Seeking Integers

August 6, 2018

A few twists on Turing’s proof of undecidability of predicate calculus

By permission of Rich Longmore,
artist, blog source

Alan Turing presaged Stephen Cook’s proof of {\mathsf{NP}}-completeness of {\mathsf{SAT}.} Turing reduced the halting problem for his machines to the decision problem of the first-order predicate calculus, thus showing (alongside Alonzo Church) that the latter is undecidable. Cook imitated Turing’s reduction at the level of propositional calculus and with a nondeterministic machine.

Today we present a version of Turing’s proof and show how it answers a side issue raised in our previous post.
Read more…

A Quest For Simple Hard Statements

July 28, 2018

Made-to-order statements that are not so simple

Harvey Friedman is a long-standing friend who is a world expert on proofs and the power of various logics. This part of mathematics is tightly connected to complexity theory. This first mention of his work on this blog was a problem about the rationals that says nothing of “logic” or “proofs.”

Today Ken and I would like to introduce some of Harvey’s work in progress. Update 8/16/18: Harvey has posted a full draft paper, “Tangible Mathematical Incompleteness of ZFC.”
Read more…

Group Theory Is Tough

July 18, 2018

Some musings on group theory

Isaacs honorary conference source

Martin Isaacs is a group theorist emeritus from the University of Wisconsin, Madison. I just picked up a copy of his 2008 book, Finite Group Theory. Simple title; great book.

Today I want to make a few short comments about group theory.

I always hated group theory. Well not really hated it. But I have never been able to get decent intuition about groups.
Read more…