Could We Have Felt Evidence For SDP ≠ P?
Evaluating mathematical beliefs
|
|
Rutgers in memoriam source. |
Leonid Khachiyan in 1979 caused arguably the most sudden surprise to the West’s popular scientific understanding since the successful launch of Sputnik in 1957. His ellipsoid method gave the first algorithm for linear programming whose polynomial running time was verified. Thanks largely to Narendra Karmarkar it has been superseded by faster interior-point methods, while older algorithms have since been noted to run in polynomial time, but the breakthrough and inspiration came from Khachiyan. Could something like it happen again?
Today Ken and I want to ask whether recent argument over beliefs about 
Read more…
How To Carry Fame
Long proofs are not always the most important results
Michael Rabin is visiting Georgia Tech today and tomorrow to give a pair of distinguished lectures. Both of these will be on applications of cryptography. One is to help auctions avoid cheaters, while the other is to help elections avoid cheaters. I see a pattern. Ken sees another pattern— he is helping chess tournaments avoid cheaters.
Today I want to comment about Rabin’s fame and what makes a result important.
Codes Meet Numbers
Results and problems about primes that make us think of coding theory
 |
|
Cropped from source. |
Zhi-Wei Sun is a professor in Mathematics at Nanjing University in China. He is the Editor in Chief of the recently-founded Journal of Combinatorics and Number Theory. His homepage is unique in prominently featuring a long list of
- …not his awards,
- …not his papers,
- …not his theorems,
- …but rather his conjectures.
Indeed we count 432 total conjectures in his list, subtracting one that he seems last year to have proved. They do not seem to be easy conjectures—this one implies the Riemann Hypothesis in a nontrivial way. Some of them involve powers of 2, which lend them a coding-theory flavor.
Today Ken and I wish to share ideas of using coding theory to prove number-theoretic results. Read more…
Can Plants Do Arithmetic?
The computational power of plants
Martin Howard and Alison Smith are research scientists at the John Innes Centre (JIC) in Norwich, England. JIC was founded as a horticultural institution by the philanthropist John Innes in 1910, and is today one of several independent institutes affiliated to the University of East Anglia. Howard and Smith are the senior scientists on a paper that claims to show that plants can perform arithmetic division. Their co-authors are Antonio Scialdone, Sam Mugford, Doreen Feike, Alastair Skeffington, Philippa Borrill, and Alexander Graf.
Today I thought we might look at their claim and see if theory can shed any light on it.
Read more…
Practically P=NP?
Solving is believing
|
|
Cropped from source. |
Boris Konev and Alexei Lisitsa are both researchers at the University of Liverpool, who work in Logic and Computation. They have recently made important progress on the Erdős Discrepancy Problem using computer tools from logic. Unlike the approach of a PolyMath project on the problem, their proof comes from a single program that ran for just over 6 hours, a program administered only by them, but mostly not written by them.
Today Ken and I wish to talk about their paper and two consequences of it. Read more…
The Evil Genius
Do our computers live in a simulation?
René Descartes is famous for countless things in mathematics—Cartesian products, Cartesian coordinates, Descartes’ rule of signs, the folium of Descartes. He is also famous for his work in philosophy and the notion of an evil genius. The evil genius presents a full illusion of a reality, and “fools” Descartes into believing there is a reality, while actually there is none.
Today Ken and I want to talk about the evil genius, and its relationship to the simulation hypothesis.
Read more…
Three From CCC
Comments on three papers from the Conference on Computational Complexity
Michael Saks is Chair of the Program Committee of this year’s Conference on Computational Complexity (CCC). He was helped by Paul Beame, Lance Fortnow, Elena Grigorescu, Yuval Ishai, Shachar Lovett, Alexander Sherstov, Srikanth Srinivasan, Madhur Tulsiani, Ryan Williams, and Ronald de Wolf. I have no doubt that they were faced with many difficult decisions—no doubt some worthy papers could not be included. The program committee’s work does not completely end after the list of accepted papers is posted, but it is not too early to thank them all for their hard work in putting together a terrific program.
Today I wish to highlight three papers from the list of accepted ones. Read more…
Seeing Atoms
How can we possibly see atoms?
John Sidles is a medical researcher and a quantum systems engineer. His major focus is on quantum spin microscopy for regenerative medicine. He is both Professor of Orthopedics and Sports Medicine in the University of Washington School of Medicine, and co-director of the UW Quantum Systems Engineering Lab. Watching various injury troubles at the Sochi Winter Olympics makes us wonder whether quantum sports medicine is an idea whose time has come. Well beyond some media’s overheated references to our athletes as “warriors” is a nice reality: John’s main project is for healing those injured in the armed services.
Today Ken and I wish to talk about John and his work in general. We especially like his title of quantum systems engineer. Read more…
Black Versus White Boxes
What is better than how (?)
|
|
History of filters source. |
Wilhelm Cauer was a German mathematician and engineer who worked in Göttingen and the US between the two world wars. He is associated with the term “black box,” although he apparently did not use it in his published papers, and others are said to have used it before. What Cauer did do was conceive a computing device based on electrical principles. According to this essay by Hartmut Petzold, Cauer’s device was markedly more advanced and mathematically general than other ‘analog devices’ of the same decades. He returned to Germany in the early 1930’s, stayed despite attention being drawn to some Jewish ancestry, and was killed in the last days of Berlin despite being on the Red Army’s list of scientists whose safety they’d wished to assure.
Today Ken and I wish to talk about black boxes and white boxes, no matter who invented them, and their relation to computing.
Read more…
Regression On Arithmetic Progressions
How far can trivial ideas go?
Klaus Roth is famous for many results, but two stand out above all others.
One sets limits on Diophantine approximations to algebraic numbers, and the other sets limits on how dense a set can be and have no length-three arithmetic progression. He has won many awards for his work, including a Fields Medal and the Sylvester Medal.
Today I want to try and amuse you with a simple proof that is related to his work on progressions.
Read more…
