Quantum Unproving
Some theorems lose validity after quantum processing
|
| Quantum Tarot source |
Dr. Lofa Polir is a research associate at UCLQ. This is the new University College London Quantum Institute. We have previously noted her move to England after working at the LIGO lab in Shreveport, Louisiana.
Today we describe her recent disturbing discovery—or rather, “undiscovery.”
Read more…
STOC 2024
Including TheoryFest 2024 in a blended 5-day format
|
| His NYU page |
Anupam Gupta just asked us to help announce the next 56th ACM Symposium on Theory of Computing (STOC 2024). His own news is a recent move from CMU to NYU.
This comes together with TheoryFest 2024 in an expanded 5-day format. The fun is at the Sheraton Vancouver Wall Centre in Vancouver, British Columbia, Canada from Monday, June 24 through Friday, June 28. The registration link is http://acm-stoc.org/stoc2024/registration.html
In addition to the STOC 2024 paper talks, the program features keynote talks by Michal Feldman, Jakub Pachocki, and Tim Roughgarden, and workshops on Algorithmic Problems in Modern LLMs, Extremal Combinatorics, Length-Constrained Expanders, Online Resource Allocation, and a special workshop on TCS Mentoring, Diversity, and Outreach.
Read more…
Leprechauns Sue Over AI
For domain infringement and IP violations
 |
| By GPT4 after conversation |
Neil L. was angry. I had expected him to be bored. Neil is a Leprechaun whose visits to Dick and me have been recounted in St. Patrick’s Day posts on this blog. Dick and Kathryn were on planes last night returning from Northern Michigan, so Neil had to come to me. The NCAA basketball tournament has not started yet. I’ve been lumbered with more high-profile chess cheating accusations besides those I began addressing in this post and have begun responding to here. So I was not eager to see green smoke at my living-room workdesk.
Today, St. Patrick’s Day, we convey a warning and more from Neil.
I did not have to look for smoke. At the stroke of midnight, with my wife already abed, a whoosh sounded behind me. I swiveled around and beheld not only Neil but an army of leprechauns at work with parchments and quills on long tables. Our grand piano’s closed lid supported one end of a giant scroll that was unrolled across our window couch and splayed onto the floor. As I rose to inquire, Neil beckoned me to where a lantern was hung on our ceiling hook over the couch.
“The Treaty of Leitirmhicanbhaird—in 1210 of your years. It grants us exclusive privilege in perpetuity to exercise these rights:
- Whole-cloth confabulation.
- Shoemaking after sundown.
- Blarney in oversaturation.
- Secretly protected gold repositories.
- Shape-shifting and panorama alteration in 3D.
In return we gave fealty to the visiting King John of England. This enumeration was the template for your Magna Carta five years later. But eight centuries hence ye have violated it. We seek redress.”
The Lawsuit
Before I could get to whether leprechauns are allowed to sue in US federal courts, I struggled to understand the categories. Whole-cloth? Shoe factories have worked at night for many decades; why sue only now? Neil cut in:
“We have nowt o’ grief over shoes. It sufficed to reach a deal with Michael Jordan, who still collects five percent on every pair and turns over half to us. Better yet, we now have James Harden distributing our designs:”
I understood “blarney” but why only “in oversaturation”? Neil replied, “like with the yellow ribbons.” I understood right away: A trapped leprechaun once agreed to mark the tree where his gold was buried with a yellow ribbon. But when his captor returned with shovel and barrow, every tree had a yellow ribbon. We would call that information overload indeed. On the fourth category, Neil indicated:
“Those clerks there are beavering on whether Bitcoin and other cryptocurrencies encroach upon our impress. As for the fifth, it was always understood that the Crown retained the rights to 2D image shifting, ones they exercise to this day:”
 |
| The Conversation source—click for sharper versions. |
As I took in the ingenious enormity of this, I recalled how I myself waxed cryptic in my own official contribution to her wedding. Neil brought me back to focus:
“It be mainly the first on which we quarrel. Confabulation is an art above mere lying. A lie always has connection to a truth from which it misdirects. That is the human way. You also have “fiction” but it is always labeled thus—again, per this agreement, upon which the Crown scriveners and later printers licensed the production of fiction. But to create alternate reality from whole cloth and pass it as truth—often without malign intent—is our preserve.”
I thought about all manners of human truth-dodging and realized the sense of Neil’s legal parsing. But where were the actual violations coming from? Neil easily read my mind and continued:
“The great fault is with your inhumans, those of your creation. They are not covered by the treaty. Ye have tried to impose constraints by topic but the mathematics of their design opposes conformity to truth.”
Neil added that they were also joining several copyright lawsuits by the New York Times and best-selling authors and other media outlets over copyright infringement. “Most of the clerks you see are checking our case law records to see whether ChatGPT’s pervasive bogus legal references have been drawn from them.”
Not Hallucination But Confabulation
I began to see horns of dilemmas. Our own case law records have long been computerized in the LexisNexis databases. They are a commerical company, with 10,000 employees across all of their services. For their entirety to be citable by ChatGPT and other Large Language Models (LLMs) would obviate their own subscriptions. On the other horn, without such access, ChatGPT must fend for itself—that is, feign for itself. Neil cut in again:
“Aye, but the problem be far worse. Let me tell ye the depths of the woe.”
Neil prefaced it by saying that the US Library of Congress catalog has “over 20 million catalog records for books, serials, manuscripts, maps, music, recordings, images, and electronic resources in the Library of Congress collections.” It should list nearly every book ever published and be an authority for the same. Neil emphasized:
“It has only 20 million entries; its basic bibliography information should come to one gigabyte at most. With US Government benison and a trap-door encoding, the LoC catalog could be melded into any standalone LLM download with minimal fuss.”
Neil continued, “Now let me tell you a tale of one chap among your pundit class. Let us call him Murtagh O’Lacey. In real life he is as Irish as your wife is. Among many LLMs vying to play king-o’-the-hill is Mixtral built on Ollama. It offers a 26GB download needing no further Internet connection. As such, it resembles a recent neurally-trained chess engine claiming to give “Grandmaster-Level Chess Without Search.”
Indeed Neil was right: all of the wisdom of chess compacted into one easily downloaded file. Can we do the same with all human wisdom? That an innocuous research query can receive a stunningly specific answer like the following (boldface words as well as the name changed) seems to presage yes:
Prompt: Does Murtagh O’Lacey know the work of S.I. Hayakawa?
Mixtral 8x7B (Ollama with Default Quant):
Yes, Murtagh O’Lacey is familiar with the work of S.I. Hayakawa. In fact, O’Lacey has cited Hayakawa’s work in his own writing on several occasions.
S.I. Hayakawa was a Canadian-born American academic and politician who served as a United States Senator from California from 1977 to 1983. He was also a distinguished professor of linguistics and philosophy at several universities, including the University of Chicago and San Francisco State University.
O’Lacey, who is an American journalist, historian, and reviewer, has written extensively on issues related to language, communication, and culture. In his book “The Press and Public Life,” O’Lacey cites Hayakawa’s work on semantics and the importance of clear communication in public discourse.
Additionally, in a 2015 article for Wired Magazine, O’Lacey referenced Hayakawa’s concept of “insult pacifism” in relation to debates over free speech and political correctness on college campuses.
BUT—, thundered Neil:
“There be nae book o’ that title, nair has S.I. Hayakawa e’er been mentioned in the actual magazine referenced.”
Neil wagged a finger at me: “Ye write research papers with Dick who is a founding expert on program checking. Yet ye release programs that can afford another 4% of size for the most basic of checks with the LoC catalog, but don’t! It has taken some of your experts too long to realize that this is not ‘hallucination’ but confabulation. Our rights have been infringed.”
And with that, Neil and the whole coterie vanished in smoke, which curled around to form the words, “see you in court.”
Open Problems
Is Neil right to warn us—and is it really doom that is being warned?
[some format and word changes, added “checking” bit at end]
Does Pi Conspire?
With integers like 222, perhaps
|
| his site |
James Franklin is a mathematician and philosopher at the University of New South Wales in Sydney. He wrote an article in 2016 for the Mathematical Intelligencer titled, “Logical probability and the strength of mathematical conjectures.” One example in his article concerns statistical properties of the decimal digits of 
Today, Pi Day, we ask whether
Franklin’s essay begins with a volley of questions:
What are probabilities, really? Actual or long-run relative frequencies? Measures satisfying Kolmogorov’s axioms? Physical propensities? Degrees of belief? All those views and more have their defenders, and the differences have an impact on what to believe and do on the basis of data.
He then goes on to his main question:
What sense can be made of the notion of the probability that an unproved mathematical conjecture is true?
Extreme Risk and Doom
In our previous post, we considered whether P=NP can be assigned, not a probability, but a present financial value. Franklin works on this wavelength too, under the heading of extreme risk theory. He says on his webpage:
My research on extreme risks looks at the problems of combining very small amounts of data with expert opinion to reach reasonable estimates of the chance of very rare events with large negative consequences.
P=NP counts as an extreme risk because equality—or anything denting confidence in the practical most-case intractability of factoring or related problems—would collapse Bitcoin and similar cryptocurrencies. Our query of whether there is a present value of hedging such risk drew a private parallel from Ron Rivest, who pointed to a new manuscript on his website titled “Betting on Doom.” It derives a present value on a bet even when one side brings the end of the world. Whether a fully effective form of P=NP would cause human extinction—perhaps by supercharging AI—is up for debate.
Franklin’s 2008 paper on evaluating extreme risk events emphasizes how to assess their probability, when one cannot infer from frequency of occurrence because the event may occur once or never. Note that P=NP is a one-shot event by definition: it cannot “occur” twice. That’s the tack that he picks up in his 2016 essay, where the conjectures need not involve risk.
Can the digits of 
Testing Pi
The digits of 
Reinhard Ganz discovered a relatively simple test that the first 
The first step in his test broke the digits into two-hundred twenty-two blocks, each partitioned into five billion 9-tuples of digits. Note that 
The further steps test whether
Bailey and Borwein, with Richard Brent and Mohsen Reisi, reviewed Ganz’s experiment. They reproduced his findings, but found an unsuspected loophole:
The number 222 is a “magic number.” Replace it by neighboring numbers of blocks, for instance
213, 217, 226, 231, 236, 241, 246, 252, or 258 blocks, and the final statistical tests of the resulting strings
of length
all pass.
Put another way, there was an unseen thumb on the scale: The number 222 was not merely a numerical convenience to get up to a number 99,900,000,000,000 that is real close to 
Conspiracy?
Still, there remains an unsettling element in this explanation. The number 222 still represents a “pothole” for
Could
Is there a natural, non-contrived application that takes auxiliary input
in the form of an unlimited sequence of digits, such that
versus the digits of
or Euler’s constant, not to mention truly random digits?
Our notion of “natural” allows 
Open Problems
Putting our question another way, might the digits of
[fixed links to BBBR paper and Calude et al.]
P=NP and Bitcoin
The present value of working on conjectures…
Anil Nerode of Cornell University has served over sixty years—he’s believed to be the longest such faculty member in university history. He helped found Cornell’s computer science department, advised more than 55 doctoral students—a Department of Mathematics record—and made important contributions to logic, mathematics, computer science, and more. He and Juris Hartmanis jointly oversaw Ken’s Mathematical Sciences Institute postdoc at Cornell in 1986–89.
I found it interesting that Anil has worked on teaching methods:
“I was educated at Chicago under the business of doing the cleanest, shortest expositions of absolutely everything,”
He has developed his own method: He now teaches in historical order. Translating ancient theories into modern notation allows him to show his students the origins of mathematics. This is a cool method.
|
| Cornell Chronicle source—our felicitations |
Anil has done extensive work in complex control systems, which is certainly a challenging area for an approach based on clarity and simplicity. He is often credited for co-creating, together with Wolf Kohn, an approach called hybrid systems theory. His partnership with Kohn has even extended to integrating quantum and macroscopic control mechanisms for magnetic batteries on many scales.
Read more…
Dominic Welsh, 1938–2023
My doctoral thesis advisor
|
| Geoffrey Grimmett source |
Dominic Welsh passed away last November 30th. He was my doctoral advisor 1981–86 at Merton College, Oxford University, and a giant in several fields of combinatorial and applied mathematics.
Today I remember Dominic and describe his late-career influence on a modern problem: How “natural” is bounded-error quantum polynomial time?
Among several memorials by colleagues and friends, there is now a detailed tribute on the Matroid Union blog by my fellow student and Oxford officemate Graham Farr with fellow students Dillon Mayhew and James Oxley. Graham lays out the full variety of Dominic’s career, beginning with his work on discrete probability and then going on to matroid theory—work that led him to write the definitive text Matroid Theory already in 1976.
Read more…
Structure of Polynomials
A feature in the current AMS Notices issue highlighting women in mathematics
Marie-Françoise Roy is a French mathematician, emerita of the Institute for Mathematical Research of the University of Rennes, where she has been since 1985. She works in real algebraic geometry, but her own statement of her research theme prefaces a key word: algorithmes de la géométrie algébrique réelle.
This theme is picked up in a wonderful article by Saugata Basu in this month’s special issue of the AMS Notices—which is dedicated to Women in Mathematics. He is a professor in the mathematics and computer science departments of Purdue University.
His article highlights Roy’s beautiful work on the structure of polynomials over the real numbers. These results are close to things near and dear to us in complexity theory. We don’t just mean single-variable polynomials that bound the running time and space usage of algorithms we regard as theoretically efficient. We mean multi-variable polynomials into which many combinatorial problems can be translated—in a manner often richer than the translations into Boolean formulas that we teach first in complexity theory.
Read more…
New Methods Solve Old Problems
Really old ones, in this case
Ben Cohen writes the “Science of Success” column for The Wall Street Journal. It is about what makes people, teams and ideas work out in business, culture, and beyond.
His recent one was about Luke Farritor, who was a college student majoring in computer science and interning at SpaceX, and who began working on a problem that captivated many of the world’s top geeks.
The problem was about trying to read ancient papyrus scrolls that have gone unread for millennia. As Cohen—or his headline writer—tells it: “Then came a $1 million competition for AI geeks, and some of the World’s Smartest Young Minds Cracked this 2,000-Year-Old Mystery.”
Stop Cheating—Again
More than just stopping carelessness
Sholto David is featured in this past Tuesday’s New York Times Science section for his work on cheating in papers on medical research.
Congrads to NAE’24
The 2024 class of new members
The National Academy of Engineering has just announced its new members for 2024. The webpage has a graphic announcing:
In Britain, your class year is your year of entry, as appropriate here. But on this side of the Pond it is one’s year of graduation—that is, of leaving. Our American usage does not “scale up,” as one might put it. Anyway, I say “congraduations” to the new members.
Read more…
