## Limits On Matrix Multiplication

*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…

## Power Circuits

*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:

*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

*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 -completeness of 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

*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

*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…