The Fallows of Medium Data

Who will curate less-prominent datasets?

Presidential Biography src

Samuel Fallows was a bishop in the Reformed Episcopal Church. He was born in 1835 and headed the denomination for four stints between 1877 and his death in 1922. Among numerous popular works, he compiled his own Complete Dictionary of Synonyms and Antonyms. Unlike the more-famous Roget’s Thesaurus, it is freely downloadable—but there are catches.

Today we discuss travails and lessons from my effort to use this book as data in my algorithms-and-data-structures course this past term.

The Graph of Ancestors

Is there an “Implex Method” in complexity theory?

Wikipedia src

Bill Wyman was the bass guitarist of the Rolling Stones until 1993. He married Mandy Smith in 1989. A few years later, in 1993, his son, Stephen Wyman, married Mandy Smith’s mother, Patsy Smith. Had Bill and Mandy not divorced by then, Wyman would have been his own stepfather. Which Wyman do we mean? Both of them.

Today we investigate the level of degeneracy in “family tree” type graphs.

Sorting and Proving

A proof tells us where to concentrate our doubts—Morris Kline

Tony Hoare is also known informally as Sir Charles Antony Richard Hoare. He has made key contributions to programming languages, algorithms, operating systems, formal verification, and concurrent computing.

He won the 1980 Turing Award for “Fundamental contributions to the definition and design of programming languages.”

Laws and Laughs

Rules are a great way to get ideas. All you have to do is break them—Jack Foster

Roy Amara was a researcher and president of the Institute for the Future. Among things he is known for is coining Amara’s law on the effect of technology.

Today Ken and I want to discuss “laws”. We hope you will like the smile that many of these give us. Perhaps they will give you some too.

Women In Theory

I like crossing the imaginary boundaries people set up between different fields—it’s very refreshing. There are lots of tools, and you don’t know which one would work—Maryam Mirzakhani.

Shafi Goldwasser is the director of the Simons Institute for the Theory of Computing. She just ran their tenth year celebration. The talks are viewable now on SimonsTV.

Easy as ABC

A modern mathematical proof is not very different from a modern machine: the simple fundamental principles are hidden and almost invisible under a mass of technical details—Hermann Weyl.

Shinichi Mochizuki is a mathematician who is at the center of a decade old claim. He has—he says since 2012—solved a famous open problem in number theory called the abc conjecture. This conjecture is in number theory and would revolutionize our understanding of the structure of the natural numbers.

What is the ABC?

The abc conjecture is a conjecture in number theory, first proposed by Joseph Oesterle and David Masser independently around 1985. It is stated in terms of three positive integers, (hence the name) that are relatively prime and satisfy . If denotes the product of the distinct prime factors of , the conjecture essentially states that is usually not much smaller than .

The common term for the product of the distinct prime factors of a positive integer is the “radical” of , written by Wikipedia, in Timothy Gowers’s Princeton Companion article, and in other sources in abc. We demur from doubling up on an established term with a different meaning and suggest calling it the “wingspan” . Then square-free integers have the largest possible wingspan, while large prime powers minimize it. Now we can state the conjecture formally:

For every , all but finitely many triples of relatively prime positive numbers giving have

Intuitively what it says is that numbers that have large powers of different primes cannot be related by addition. As , it says that the wingspan of the triple’s product must at least approach , which is greater than the cube root of . Note, incidentally, that if any two of share a prime factor then so does the third, so we can divide out all such to get meeting the hypothesis.

The point of the conjecture is that it relates addition and multiplication. It allows making inferences about the multiplicative structure of natural numbers from additive properties and vice-versa. The formal theory of the natural numbers with respect to addition alone, called Presburger arithmetic, is decidable, as is the theory of multiplication alone, called Skolem arithmetic. The theory of both and , Peano arithmetic, is of course undecidable. But abc gives a playbook for leveraging the decidable sub-systems.

ABC Implies What?

The conjecture has high explanatory power in that many other conjectures (listed here) follow from it. Among them, we note:

1. Whereas no one has significantly simplified Andrew Wiles’s famously difficult proof strategy for Fermat’s Last Theorem (FLT), the theorem for follows quickly from a weaker analogue of the abc conjecture.
2. A generalization of FLT concerning powers that are sums of powers, called the Fermat-Catalan conjecture, also follows from abc.
3. If a polynomial with integer coefficients has at least three simple zeroes, then there are only finitely many positive integers such that is a perfect power (i.e., such that for some integers ).

This raises the following natural question for us computational complexity theorists:

Does the abc conjecture imply any “shocks” in complexity theory—namely, resolving basic open questions that have been open for over half a century?

Ken and I are not aware of any. It does not seem to affect factoring, or complexity theory, or any main ingredients of our favorite P=NP problem. But it does have great impact on anything that concerns Diophantine questions. It is possible that connections may emerge at this level of detail.

Is The ABC Proved?

Here is a timeline of Mochizuki proof:

Mochizuki made his work public in August 2012 without any fanfare. Soon it was picked up and the mathematical community was made aware of the claim he has proven the abc conjecture. This started the quest to determine if his proof is correct.

The proof is long and complex. Workshops were held in 2015 and 2016 on it. The presentations did not lead to acceptance of Mochizuki’s ideas, and the proof remains unclear.

Enter Peter Scholze and Jakob Stix—two world experts on number theory. They visited Kyoto University for five days of discussions with Mochizuki in 2018. It did not resolve the correctness of the proof but did bring into focus where the difficulties lay.

They wrote a report Why abc is still a conjecture. It starts:

We, the authors of this note, came to the conclusion that there is no proof. We are going to explain where, in our opinion, the suggested proof has a problem, a problem so severe that in our opinion small modifications will not rescue the proof strategy.

Then, Mochizuki wrote a response of his view of why their claims were wrong: Comments On The Manuscript by Scholze-Stix. He said:

It should be stated clearly that the assertion that “these are inessential to the point we are making” is completely false! I made numerous attempts to explain this during the March discussions, and it is most unfortunate that we were ultimately unable to communicate regarding this issue.

The disagreement over the correctness remains: Other authors have pointed to the unresolved dispute between Mochizuki and Scholze over the correctness of this work as an instance in which the peer review process of mathematical journal publication has failed in its usual function of convincing the mathematical community as a whole of the validity of a result.

Explaining Math

Albert Einstein may have said:

“If you can’t explain it to a six year old, you don’t understand it yourself.”

Some attribute this instead to Richard Feynman. But whoever said it the mathematical community generally agrees with the point. In the 1962 book New Perspectives in Physics, by Louis De Broglie, states that Einstein, when discussing theories, said:

“ ought to lend themselves to as simple a description as that even a child could understand…”

I wonder if the requirement “explain it to a six year old” does not mean the six year old must understand it. Rather that when you explain it to them they listen politely. That is the requirement is they listen. What do you think?

Open Problems

Mochizuki still claims his proof. He violates the above rule: he cannot explain it to a six year old—not even a senior expert. It still has not yet been accepted as passing the peer review stage. See this for some general comments. And this for some more. It has lots of comments.

Can the abc ever be resolved? I wonder if there is some way to say suppose that the abc is true. And then prove some surprising complexity consequence holds? Perhaps violate P=NP for example, or some other result.

CCC 2022 Conference

I have a private plane. But I fly commercial when I go to environmental conferences—Arnold Schwarzenegger

Computational Complexity Conference CCC is about to happen:

July 20—23, Philadelphia, PA, USA

It is an annual conference on the inherent difficulty of computational problems in terms of the resources they require.

Ryan Williams just sent out a request on behalf of CCC: The travel allowances for CCC are available for students from US universities. The deadline for applying is June 8. Here is the link.

Accepted Papers

Here is a list of the accepted papers with pointers to versions of the papers:

• Gal Beniamini. The Approximate Degree of Bipartite Perfect Matching
• Till Tantau. On the Satisfaction Probability of k-CNF Formulas
• Andrej Bogdanov, William Hoza, Gautam Prakriya and Edward Pyne. Hitting Sets for Regular Branching Programs
• Svyatoslav Gryaznov, Pavel Pudlak and Navid Talebanfard. Linear Branching Programs and Directional Affine Extractors
• Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem
• Karthik C. S. and Subhash Khot. Almost Polynomial Factor Inapproximability for Parameterized k-Clique
• Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff. l_p-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Ian Mertz and James Cook. Trading Time and Space in Catalytic Branching Programs
• Harm Derksen, Visu Makam and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
• Guy Blanc and Dean Doron. New Near-Linear Time Decodable Codes Closer to the GV Bound
• Jun-Ting Hsieh, Sidhanth Mohanty and Jeff Xu. Certifying solution geometry in random CSPs: counts, clusters and balance
• Vikraman Arvind and Pushkar Joglekar. On Efficient Noncommutative Polynomial Factorization via Higman Linearization
• Ivan Mihajlin and Anastasia Sofronova. A better-than-3log(n) depth lower bound for De Morgan formulas with restrictions on top gates
• Dan Karliner, Roie Salama and Amnon Ta-Shma. The plane test is a local tester for Multiplicity Codes
• Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width
• Halley Goldberg, Valentine Kabanets, Zhenjian Lu and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
• Erfan Khaniki. Nisan–Wigderson generators in Proof Complexity: New lower bounds
• Ryan O’Donnell and Kevin Pratt. High-Dimensional Expanders from Chevalley Groups
• Victor Lecomte, Prasanna Ramakrishnan and Li-Yang Tan. The composition complexity of majority
• Scott Aaronson, Devon Ingram and William Kretschmer. The Acrobatics of BQP
• Zander Kelley and Raghu Meka. Random restrictions and PRGs for PTFs in Gaussian Space
• Amol Aggarwal and Josh Alman. Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
• Lijie Chen, Jiatu Li and Tianqi Yang. Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
• Pavel Hubacek. Snakes on Ladders: On the Complexity of the Parity Argument on Directed Cycles
• Gal Arnon, Alessandro Chiesa and Eylon Yogev. Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
• Shuichi Hirahara and Mikito Nanashima. Finding Errorless Pessiland in Error-Prone Heuristica
• Shuichi Hirahara. Symmetry of Information from Meta-Complexity
• Louis Golowich and Salil Vadhan. Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs
• Nikhil Bansal, Makrand Sinha and Ronald de Wolf. Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
• Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings
• Sarah Bordage, Mathieu Lhotel, Jade Nardi and Hugues Randriam. Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
• Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi and Srikanth Srinivasan. Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
• Nutan Limaye, Srikanth Srinivasan and Sebastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
• Mika Goos, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao. Further Collapses in TFNP
• Xin Lyu. Improved Pseudorandom Generators for Circuits
• Yanyi Liu and Rafael Pass. Characterizing Derandomization Through Fine-Grained Hardness of Levin-Kolmogorov Complexity
• Yanyi Liu and Rafael Pass. On One-way Functions from NP-Complete Problems
• Oliver Korten. Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle
• Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Open Problems

Is this list with pointers helpful? It took a few minutes to form this list—had to add the pointers.

Being Different

In mathematics you don’t understand things. You just get used to them—John von Neumann.

Harvey Friedman is a famous mathematical logician who spent most of his career at Ohio State University. He worked not on proving new theorems as much as finding the axioms needed to prove them. Later in his career it was the axioms needed for certain large cardinal theorems. These questions can be very subtle and difficult—not unlike lower bounds in complexity theory.

Harvey was listed in the Guinness Book of World Records for being the world’s youngest professor when he taught at Stanford University at age 18 as an assistant professor of philosophy. He got his Ph.D. from Massachusetts Institute of Technology in 1967—hence the young age.

The Difference

Harvey has taken a viewpoint for most of his career that is different from other logicians. Godel’s incompleteness theorems apply to most logic systems—certainly those that are strong enough for central areas of mathematics. But the majority of mathematicians believe that incompleteness does not apply to their everyday work. In short most do not think:

I cannot prove P not equal to NP, so it must be incomplete.

Rather they feel that this means I am not smart enough to resolve P vs NP. Which of these is true?

For example, Harvey has created numerous algebraic and geometric systems that make no explicit reference to logic but which, under a suitable coding, contain a logical system to which Godel’s incompleteness theorems apply. Furthermore, these systems look similar to many systems used by mathematicians in their everyday work. Harvey uses these examples to argue that incompleteness cannot be dismissed as a phenomenon that occurs only in overly general foundational frameworks contrived by logicians. He argues that it applies often to their everyday world.

An Example

Harvey is also able to find numerous combinatorial statements with clear geometric meaning that are proved using large cardinals axioms and shown to require them. These results are famous to Harvey. Such axioms previously seemed to require statements that are not geometric.

Gill Williamson can show that this can be used to connect these problems to the assumption that subset sum is solvable in polynomial time. See the paper On The Difficulty Of Proving P Equals NP In ZFC. This curious connection between the P vs. NP problem and the theory of large cardinals seems to suggest that either P=NP is false or otherwise not provable in ZFC. This connection is surprising.

Incompleteness

Harvey does have a conjecture that shows that certain statements are not incomplete. He is interested in both sides of this coin: sometimes statements are provable and sometimes not. Concretely many mathematical theorems, such as Fermat’s Last Theorem, can be proved in very weak systems such as EFA. The Grand Conjecture says: Every theorem published in the Annals of Mathematics whose statement involves only finitary mathematical objects (i.e. what logicians call an arithmetical statement) can be proved in EFA.

EFA is the weak fragment of Peano Arithmetic based on the usual quantifier-free axioms for , together with the scheme of induction for all formulas whose quantifiers are bounded. While it is easy to construct artificial arithmetical statements that are true but not provable in EFA the point of the grand conjecture is that natural examples of such statements seem to be rare.

Open Problems

When Harvey was just starting to read, at age 4 or 5, he remembers pointing to a dictionary and asking his mother what it was. It’s used to find out what words mean, she explained. A few days later, he returned to her with his verdict: The volume was completely worthless. For every word he’d looked up, the dictionary had taken him in circles: from “large” to “big” to “great” and so on, until he eventually arrived back at “large” again. She just looked at me as if I were a really strange, peculiar child, Friedman laughs.

This is an insight reported in an article by Jordana Cepelewicz. I cannot imagine Harvey was four or five when he told his mom this. For more stuff—when not so young—see the book.

Hilbert’s Lost Problem

Mathematics consists in proving the most obvious thing in the least obvious way—Pólya.

David Hilbert famously presented 23 important open mathematical problems at the International Congress of Mathematicians in Paris in 1900. He intended to include a 24th on the simplicity of proofs.

Today we discuss this problem, which was “lost” until the historian Rüdiger Thiele discovered it in Hilbert’s papers in 2000 and brought it to light in a paper for the American Mathematical Monthly.

I (Ken) have long wondered why Hilbert targeted the number 23 for his list. That some of his problems have broad, vague statements tells me he could have altered their number. To be sure, he discussed only 10 in his actual 1900 lecture; the rest appeared in his long article that year. Until Dick drafted this post and I found Thiele’s article, I had not known about a No. 24—a nice factorial number.

As discussed by Inês Hipolito and Reinhard Kahle, in a special issue of the UK Royal Society Philosophical Transactions A devoted to Hilbert’s 24th, there were only faint traces of it until Thiele’s discovery. They decline to guess Hilbert’s motives for leaving it out, but I venture this: Hilbert could not agree with himself on the terms by which to state it, even broadly. How to quantify simplicity was already the subject of Dick’s draft, into which we blend.

Pólya on Proofs

One simple question is whether a human notion of simpler proof would accord with, say, that of a Martian. George Pólya was one of a vanguard of Hungarian emigré scientists who came to be called The Martians after another of them, the physicist Leo Szilard, gave this answer to Enrico Fermi’s question of why aliens had not been detected when life in the universe should be plentiful:

“They are among us, but they call themselves Hungarians.”

Kidding aside, this could set up a Sapir-Whorf type hypothesis that humans from disparate linguistic groups and mathematical cultures could have different values for proofs. Even if so, the joke would be on non-Hungarians, because Paul Erdős, whose idea of “Proofs from The Book” set the internationally recognized standard of proof elegance, was also a “Martian.”

Pólya’s quote above hits the nail on the head. For an example, consider the theorem that:

Theorem 1 The square root of is irrational.

The well-known proof begins by supposing not:

One might claim that this famous proof is not obvious—do you agree?

A Measure

Now consider the general task of proving statements of this form:

Theorem 2 For all ,

Think this as an encoding of an interesting property: For example, for each there is a prime . Or for each planar graph there is some four coloring of . Or

To make this more concrete, let us base proofs on the Peano axioms for arithmetic, and suppose that is well-defined in this system. Note that proving to be total computable is not the same as proving that all its values are positive as Theorem 2 asserts. In case Theorem 2 is provable, we have two key parameters:

D: The length of the definition of .

P: The length of the full proof of Theorem 2.

Our proof simplicity measure is then

Some Instances

Here are some keys to understanding the value intuitively:

1. For known provable problems we might have that is not too large
2. For classic problems like the Four-Color problem we might have that is huge. Think of the proof that arises in this case.
3. For many chess positions where one side can win, say checkmate in 30 moves, the proof of that is likewise huge. Crafting chess problems where the proof is both crisp and hard to find is a centuries-old art.
4. For open problems, is currently infinite.
5. But for practical software we get something bounded. The trouble here is that is potentially huge and could be the size of .

Consider for the last case a program that calculates your tax payment based on the US tax code, for example. The code has wording like:

An apparently insignificant discrepancy between the wording in the Statutes at Large and the wording in some editions of the U.S. Code with respect to a provision of the Internal Revenue Code (specifically, the words “any papers” in the first sentence of 6104(a)(1)(A) is described by the U.S. Court of Appeals for the District of Columbia in the case of Tax Analysts v. Internal Revenue Serv., 214 F.3d 179 (D.C. Cir. 2000), in footnote 1. According to the Court, some versions of the U.S. Code show the text as “any paper” while the Statutes at Large version shows the text as “any papers.”

Thus the proof could be the same size of . Thus,

Case: . This is the usual proof of a classic problem like the four-color problem. Huge proof.

Case: . This is like a simple problem or like a proof of a complex program with tons of bits in its description.

Proofs and Software

My famous—infamous?—paper with Alan Perlis and Rich de Millo raised the related issue in the first sentence of our abstract:

It is argued that formal verifications of programs, no matter how obtained, will not play the same key role in the development of computer science and software engineering as proofs do in mathematics.

This argument made over four decades ago has been argued by critics as being wrong. Take a look at this for comments about the recent debate on the paper moderated by Harry Lewis.

We claim that we were correct but for a different reason that we made in the original paper. We got it right but for the wrong reason. The real reason is alluded to in this statement by Tony Hoare, whose programme of proofs for programs partly spurred our paper:

Ten years ago, researchers into formal methods (and I was the most mistaken among them) predicted that the programming world would embrace with gratitude every assistance promised by formalisation to solve the problems of reliability that arise when programs get large and more safety-critical. Programs have now got very large and very critical—well beyond the scale which can be comfortably tackled by formal methods. … It has turned out that the world just does not suffer significantly from the kind of problem that our research was originally intended to solve.

See also his 1996 position paper, “How Did Software Get So Reliable Without Proof?”

Open Problems

Does this measure shed some light on the problems of program verification? Is it useful? Would it have satisfied Hilbert? Hilbert’s handwritten note discovered by Thiele showed him thinking in terms of proofs via polynomial invariants and equations—hence maybe not at a brute level of counting symbols.

[some format fixes, young Hilbert picture]

Take Wing

It is a capital mistake to theorize before one has data—Sherlock Holmes

Jeannette Wing is a Professor of Computer Science at Columbia University. She was recently appointed Executive VP for Research across all of Columbia’s campuses. She is also an adjunct Professor at Carnegie Mellon University. She stays busy. See this for her CV.

Sixteen years ago she wrote a short position paper for Communications of the ACM titled “Computational Thinking.” It begins:

Computational thinking builds on the power and limits of computing processes, whether they are executed by a human or by a machine.

This is the first of sixteen sentences of the form “Computational thinking [verb]…,” plus one that follows a semicolon. The thirteenth prefaces six bulleted paragraphs giving characteristics of computational thinking. They fill page 3 of 3—the paper is shorter to read than this post.

Her 2007 talk on “Computational Thinking” has oodles of things that aren’t in the paper: pictures. It also concludes by posing five questions that she put into another famous CACM paper.

Five Questions

This second paper appeared in 2008 with the title “Five Deep Questions in Computing.” They are:

1. P = NP?
2. What is computable?
3. What is intelligence?
4. What is information?
5. (How) can we build complex systems simply?

The first is one of the basic questions of theory, of course.

The next is about what are computations? This question complicates when one includes: DNA or quantum computers? Also what about man-machine joint computations? Given that humans and machines have different computing capability, now ask: What is computable? Pretty complex.

Let’s skip what is intelligence for now.

What is information? This is a perfect question: Information is not just ‘s and ‘s. DNA encodes information in a different way and with quantum computing, it’s not bits but qubits. Amazing.

Finally we will also skip the last question.

She ends with:

I pose these questions to stimulate deep thinking and further discussion. What deep questions about computing would you want answered? In 50 years, how different will they and their answers be from what we ask and are able to answer today?

Data Science

Wing is a leading expert of data science. This field is traceable back to 1962 when John Tukey described an area he called “data analysis”. That is Tukey of Fast Fourier transform fame, who I knew when I was at Princeton.

Data science combines the scientific method, math and statistics, specialized programming, advanced analytics, AI, and even storytelling to uncover and explain the business insights buried in data.

Her current research interests are in trustworthy AI. Her areas of research expertise include security and privacy, formal methods, programming languages, and distributed and concurrent systems. She is widely recognized for her intellectual leadership in computer science, and more recently in data science. Wing’s seminal essay, titled “Computational Thinking,” was published more than a fifteen years ago and is credited with helping to establish the centrality of computer science to problem-solving in all other disciplines.

Data can be precious for one of three reasons: the data set is expensive to collect; the data set contains a rare event (low signal-to-noise ratio); or the data set is artisanal—small, task-specific, and/or targets a limited audience.

• A good example of expensive data comes from large, one-off, expensive scientific instruments, for example, the Large Synoptic Survey Telescope, the Large Hadron Collider, and the IceCube Neutrino Detector at the South Pole.
• A good example of rare event data is data from sensors on physical infrastructure, such as bridges and tunnels; sensors produce a lot of raw data, but the disastrous event they are used to predict is (thankfully) rare. Rare data can also be expensive to collect.
• A good example of artisanal data is the tens of millions of court judgments that China has released online to the public since 2014.

Open Problems

Let’s take a cue from Wing: What other major aspects and objectives of computer science shall we put into crisp bullet points?