Ken Turns 40
Every chess master was once a beginner—Irving Chernev
Ken Regan started his Ph.D. 40 years ago from Oxford, in complexity theory, advised by Dominic Welsh. Ken continues to be a researcher in complexity theory, a teacher of computer science, a mentor of graduate students, a writer of books and more. He has long been on the faculty of the Department of Computer Science and Engineering at Buffalo.
Today I thought I would thank Ken for his many wonderful accomplishments.
Ken is a great friend and long time co-author of mine. We also write this blog together. He has done many things—one colorful thing is the poster. Ken is a strong chess player—a chess International Master just below the grandmaster level and rated at 2372—roughly.
We will highlight his continued work in complexity theory and his work in detecting chess cheating.
Complexity Theory
Ken and I have just released a second edition of our book on quantum algorithms: Introduction to Quantum Algorithms Via Linear Algebra, Second Edition
Quantum computing explained in terms of elementary linear algebra, emphasizing computation and algorithms and requiring no background in physics. This introduction to quantum algorithms is concise but comprehensive, covering many key algorithms. It is mathematically rigorous but requires minimal background and assumes no knowledge of quantum theory or quantum mechanics.
I must add that Ken did the lion share of the work on writing this second edition.
|
Please note a special offer: Buy one, get another for full price.
In another part of complexity theory, Ken has just had a paper accepted: Multi-Structural Games and Number of Quantifiers with Ronald Fagin, Jonathan Lenchner, and Nikhil Vyas. This will appear at LICS 2021 this summer.
The paper defines a new type of game that captures the number of quantifies needed for certain properties. This is neat—see the paper for details.
Chess Cheating—How?
The area of detecting chess cheating is one that Ken works in. Moreover he is perhaps the leader in the world. That is the leader in detecting when a player cheated at playing chess.
What is this? In games like poker, games that rely on cards, it is long been an issue that people can cheat. Cards can be marked for example. The dealer can try and control what cards a player gets. These are ancient issues for card games.
|
What is this for chess? The pieces cannot be marked to any advantage: a king is king, a pawn is a pawn and so on. But a player can cheat in a simple manner. They can use the moves of a computer program instead of their own. The problem in chess is that computer programs currently play at a level vastly higher than even a strong player. Stockfish, a top program, plays at around 3551.
Recall Ken is around 2372. That places him via the Elo rating at IM:
- 2500-2700 most Grandmasters (GM)
- 2400-2500 most International Masters (IM) and some Grandmasters (GM)
- 2300-2400 most FIDE Masters (FM) and some International Masters (IM)
- 2200-2300 FIDE Candidate Masters (CM), most national masters
Note: the computer therefore plays much better than all known GM’s.
Chess Cheating—Detecting?
Enter Ken. He has been studying how to detect whether or not a player is using a computer’s moves rather than their own moves. He has worked on this for many years, with good success. Note: this is a real problem:
In one chess tournament, five of the top six were disqualified for cheating. In another, the doting parents of 10-year-old competitors furiously rejected evidence that their darlings were playing at the level of the world No 1.
An obvious idea is to not let a player have access to any computer. This is naive for several reasons:
- A player can use their cellphone secretly—in the toilet?
- A player could conceal the computer on themselves—computers are small?
- A player could be playing chess online—impossible to stop them?
|
Chess Cheating—How to Detect
This led Ken to consider the following problem: Suppose that some player makes a series of moves during a game. Check how well their moves agree with Stockfish or some other computer program. Then claim the player cheated provided they agree too often with the program.
This sounds simple. Compare the computer’s move and the player’s moves. If these agree too often then say the player has cheated.
Simple. Unfortunately not. There are many complications:
- In chess sometimes moves are “in book”. Especially at the beginning the best move may be well known.
- In chess sometimes moves are “forced”. There may be a unique legal move.
- A player may only use the computer when the position is “hard”.
- The computer may suggest several moves. These moves may all be about the same quality.
Clearly all these make the problem—did the player cheat—complex. Difficult. A further complicating factor is that even a weak player will sometimes randomly agree with the computer. That is even a weaker player can make a great move.
Perhaps the shock is that Ken has been able to build software that is able to correctly decide when a player cheated or not. His method is good enough that it is used in practice on real players. It has led to actual penalties on players, and has saved others from false claims.
I must add that his software is quite impressive. The test to see if a player cheated involves the running of chess computer programs. These programs like Stockfish were made to be used by one player. They were not designed to be used as a subroutine in an automated search. Perhaps for a complexity theorist Ken might have a top ranking for writing the most real programs.
Open Problems
Correction: Ken is 40th from Princeton as an undergrad. Ken is 35th from Oxford for Ph.D. See Ken on a 40th Reunion for Princeton Class of ’81 panel [Ken: A one-word fix did the trick, changing “obtained” to “started” in the first sentence. It’s a Trans-Pond-er difference: I count as ’81 both at Princeton and Oxford (Merton College) because the latter goes by the starting year. The photo is from Glenveagh Castle, Ireland, on a June 2019 trip with my family.]
Ken says: “The pandemic has brought me as much work in a single day as I have had in a year previously,” said Prof Kenneth Regan, an international chess master and computer scientist whose model is relied on by the sport’s governing body, FIDE, to detect suspicious patterns of play. “It has ruined my sabbatical.”
See this article for more detail on Ken’s work. This is by Howard Goldowsky.
Summing Up the Primes
Given the millennia that people have contemplated prime numbers, our continuing ignorance concerning the primes is stultifying—Richard Crandall and Carl Pomerance
|
| Sources: her site, Oberlin interview |
Lola Thompson is an Associate Professor of Mathematics at Utrecht University. She did her 2012 PhD thesis, Products of Distinct Cyclotomic Polynomials, under Pomerance at Dartmouth. Of course, she works in number theory. Her thesis is numbered 
Today we thought we would highlight a recent result of hers and its connections to complexity theory—indeed, to the realm of 
The interview linked below her photo at right includes these words:
Even [as an undergrad math major], I didn’t see myself having a future as a mathematician. I think that part of the issue was that I had never seen a female mathematician (none of my math professors at UChicago were women). A major turning point came when my department sent me to the Nebraska Conference for Undergraduate Women In Mathematics (NCUWM). While at NCUWM, I received a huge amount of encouragement. The idea of going to graduate school and becoming a mathematics professor had never occurred to me. It was also extremely helpful for me to see examples of female mathematicians. For the first time, I could imagine myself as a mathematician!
She is paying that forward in mentoring women. See this poster for Utrecht’s hosting of next year’s 4th Women in Numbers – Europe conference, which is affiliated to the Women in Number Theory network. I also like her comments on undergraduate education here.
The paper is joint with Harald Helfgott. The key “players” are the Möbius function and the Mertens function—named for August Möbius and for Franz Mertens.
The Key Players
The Möbius function was invented by Möbius in 1832. It is an important function throughout number theory. It is denoted by 
if n is a square-free positive integer with an even number of prime factors.
if n is a square-free positive integer with an odd number of prime factors.
if n has a squared prime factor.
It is multiplicative:
and
when 
Think of 
Of course 
A key property of the Möbius function is:
unless 
Computing —the easy way
Computing
One way to compute
Theorem 1 Suppose that
. Then we can compute
in time polynomial in
.
This would be an exponential improvement over Thompson’s result. It probably shows how unlikely it is to get this collapse. But this is still open.
Recall a set 
- Given a graph: One can count the number of spanning trees.
- Given a graph: One can count the number of three colorings of the graph.
- Given a polynomial equation: One can count the number of solutions.
- And so on.
The conjecture is that 
Computing —the hard way
Another way to compute 
She proves this main result in her paper—this is the paper we previously cited.
Theorem 2 There is an algorithm that computes
Here
and the constant in
depends on
.
Note the time used is 
The proof is non-trivial. In order to give some idea we will give a few comments. Standard identities allow one to write,
over
The insight is to look hardest at those values
Their summary of what happens next:
Our approach in Section 4 roughly amounts to analyzing the difference between reality and a model that we obtain via Diophantine approximation, in that we show that this difference has a simple description in terms of congruence classes and segments. This description allows us to compute the difference quickly, in part by means of table lookups.
As often, we say to see the full paper for the details. Or you can follow her talk either in Spanish or in English:
The proof is clever and there seems to be no way to improve it to anything near what we get via complexity theory. Of course we can only do that in the presence of a very strong conjecture:
But what she could do was to implement the algorithm in her joint paper. The computation ran on a many-core machine for weeks. It gets 
This is one advantage of algorithms that do not rely on unproved conjectures. They can actually be implemented and executed.
Open Problems
Is there a richer fount for open problems than number theory?
Scott Wins a Prize
Quantum mechanics makes absolutely no sense—Roger Penrose
|
| Scott Answers Big Questions source |
Scott Aaronson has just been named the 2020 ACM Prize in Computing for groundbreaking contributions to quantum computing, Penrose’s comment notwithstanding. The prize citation also credits Scott’s multifaceted public outreach for making our fields accessible to many.
Today Ken and I send congrats to Scott for this singular honor.
Read more…
Wobble in the Standard Model
Prediction is very difficult, especially if it’s about the future—Niels Bohr
|
| Boston Globe “Uncertainty” source |
Lisa Randall is a professor of theoretical physics at Harvard. Her research has touched on many of the basic questions of modern physics: supersymmetry, Standard Model observables, cosmological inflation, baryogenesis, grand unified theories, and general relativity. She has also written popular books about her work and science in general. Thus she has a handle on aspects of science that overlap my expertise—not to mention those of her sister Dana Randall, whom I have known as a colleague for many years.
Today, Ken and I thought we would talk about recent developments in particle physics, and their connection to two topics dear to us.
Read more…
Relaxing the Primes
Although the prime numbers are rigidly determined, they somehow feel like experimental data—Tim Gowers
|
| Finnish Scientific Courage Award source |
Kaisa Matomäki is a Finnish mathematician working in number theory. She has some terrific results on prime numbers—results that have won several important prizes including the 2021 Ruth Lyttle Satter Prize: It is presented to a woman who has made an outstanding contribution to mathematics research. The prize citation specifically mentions a 2015 paper with Maksym Radziwill that contributed to Terence Tao’s resolution of the Erdős discrepancy problem—and indeed we highlighted Tao’s followup work with her and Radziwill in our 2015 post on this.
Today, Ken and I thought we would combine one of her new deep theorems with some shallow observations.
Read more…
Computer Science Gets Noted
All non-metallic UK currency to feature Computing and Data Science pioneers
|
| Cropped from BBC source |
Charles Babbage and Ada Lovelace will be reunited. Their work on designing and programming a computing device, a century before any machine was built, is being honored by their appearance on the reverse of the 5-pound note in a new series authorized by the Bank of England. Royal Statistical Society Fellow Florence Nightingale will appear on the 10, EDSAC creator Maurice Wilkes on the 20, and Alan Turing on the 50.
Today, April 1, we are delighted to convey this news and show previews of the banknotes.
Read more…
All The News That Fits We Print
The New York Times is a great newspaper: it is also No Fun—Molly Ivins
The Gray Lady, as the New York Times is usually called, believes in her real slogan:
All the news that’s fit to print.
This slogan started about 115 years ago, and is on the masthead of the paper.
Today I thought, for something different, we would supply just news.
Read more…
Congrats Avi and Laci on the Abel Prize
The joy of knowing, understanding, and creating is common to all the sciences.—Vera Sós.
Dorit Aharonov is a researcher in quantum computation. She was a Ph.D. student of Michael Ben-Or and Avi Wigderson. Her 1999 thesis, entitled “Noisy Quantum Computation,” included her role with Ben-Or as one of several superposed groups who discovered the quantum fault tolerance threshold theorem.
Today Ken and I wish to send our congratulations to Avi and Laci—László Lovász—on winning the 2021 Abel Prize.
Read more…
Moby Dick Meet Theory
People seem to be afraid of mathematics. And I think that’s such a shame, because I don’t think it’s as hard as people seem to think it is. —Heidi Hammel
Sarah Hart holds a chair that dates back to 1597—Gresham Professor of Geometry at Birkbeck, University of London. She is a British mathematician specialising in group theory. The British modifier is redundant since I spelled specialising with a “s” not a “z”:
Today’s British English spellings mostly follow Samuel Johnson’s A Dictionary of the English Language (1755), while many American English spellings follow Webster’s An American Dictionary of the English Language (1828).
Today we will discuss history, making history, and more.
Read more…
Closing an Erdős Problem
Whatever the problem, be part of the solution. Don’t just sit around raising questions and pointing out obstacles.—Tina Fey
Daniela Kühn is the Mason Professor in Mathematics at the University of Birmingham. She works in extremal and probabilistic combinatorics. She has many honors, including giving an invited lecture at the International Congress of Mathematicians in 2014.
Today I thought we should look at a new result of hers.
By the way, as I wrote this draft, I was excited to see that it was the second time we highlighted a researcher from Bi*ngham*. Previously we highlighted Jessica Fridrich, from Binghamton University. OK, they are different places, in different countries, but the closeness in edit distance caught my eye.
Kühn says here:
Recently I have focused on sufficient conditions for Hamilton cycles in directed graphs, i.e. cycles which contain all the vertices of the directed graph. It is unlikely that there is a good characterization of all (directed) graphs containing a Hamilton cycle since the corresponding decision problem is NP-complete. So it is natural to ask for sufficient conditions for the existence of a Hamilton cycle.
Here is her paper on degree sequences on directed graphs that force Hamilton cycles. It is joint with Deryk Osthus and Andrew Treglown.
The Conjecture
Paul Erdős is known for his conjectures as well as his countless results. Here are two of his open ones that are directly about graphs:
- The Erdős-Faber-Lovász conjecture on coloring unions of cliques.
- The Erdős-Hajnal conjecture that in a family of graphs defined by an excluded induced subgraph, every graph has either a large clique or a large independent set.
Of course math is tricky: A conjecture like the—
Erdős-Szekeres conjecture on the number of points needed to ensure that a point set contains a large convex polygon.
—could still be about graphs. Consider the graph that is
Well, the conjecture (1) is now claimed to be solved, and so the list of open conjectures is one less. Kühn with co-authors Dong Yeap Kang, Tom Kelly, Abhishek Methuku, and Deryk Osthus have claimed to resolve it. I have no reason to doubt these top researchers—it’s just until it is refereed. Their paper is cleverly titled: A Proof Of The Erdős-Faber-Lovász Conjecture.
By the way: See this talk on the paper by Kühn’s co-author Abhishek Methuku on this coming Monday March 22, 2021, 14:00 UTC. To see the talk on zoom you need to know the first six primes. Here is some help:
This conjecture, now almost 50 years old, states that a graph that consists of complete graphs of size
That is: If 
The conjecture can be stated various ways:
The chromatic index of a hypergraph
Previous Results
While Kühn’s paper solves the conjecture, there were many partial results before. These prefer to view the conjecture as one about hypergraphs.
A linear hypergraph (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The
cliques of size
A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős-Faber-Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős-Faber-Lovász conjecture is equivalent to the statement that any simple hypergraph with
Call a hypergraph simple if for any pair
of distinct vertices, there is at most one edge incident to both
and
, and there are no edges incident to exactly one vertex. A conjecture of Erdős, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph on
colors.
Open Problems
See Gil Kalai for his wonderful comments on this paper of Kühn and her co-authors.
Of course we congratulate Laci plus Avi Wigderson on winning the 2021 Abel Prize. We will write more about this in an upcoming post.
