We could starve AI

There is a lot of anxiety about ai wiping off mathematics, including theoretical computer science. It’s funny that we wanted ai to cut *their* jobs, and instead it’s *our* jobs that are cut (maybe). My expectation of what is going to happen is rather flat, and I am open to various scenarios. Still I wanted to make some points.

First, at the moment of this writing, I am not so worried about ai killing the field. There are so many problems in math, and the literature is so unmanageably vast and technical, that I am not particularly shocked that using massive resources one can solve *some* problems. It is very different if the resources can solve *the* problems. For example I, and I am sure many others, have tried to use ai to solve problems in computational complexity and so far didn’t get much. I do find ai to be a very useful assistant, but so are many other things. It may be that the next level of solving target problems (as opposed to finding targets) may prove the most difficult to reach.

I want to suggest an option for the community to put ourselves in a position of strength, in case one really fears the impact of ai. I think ai can easily enough be “frozen” and made much less useful for future research. The way to do this is simple: We could stop feeding it. It was humiliating enough to post papers online only to be asked later by the publisher to pay for “gold open access.” But now that there is this new way to exploit, plagiarize, and monetize our creations on a massive scale, it may be too much. Suppose starting immediately all new math is communicated in ways that ai can’t easily scrape. There are many ways to do this; we could still put papers online, but allow only much more limited access, compatible with human beings but not ai scraping. It coud be similar to what is done for example at the Internet archive, where you can read a book but not easily download it. I am not going to go more in details. While ai would remain very useful for things on the table until that moment, I think it would quickly become much less useful for new lines of research, series of papers building on each other, etc. This would put the community in a position of strength as keeper of knowledge. After a while, things could be reassessed.

We should not forget that the models can do math only because back then we chose to be nice and so taught them how to do it for free.

Now it is a great time to study whatever computer science will be in five years

Enrollment in computer science is declining, out of fear that AI will wipe out much of the demand for software engineers. So here are the jobs of the future:

  • Real estate agent. Indeed, it will be pretty hard for AI to steal their added value: zero.
  • Driver. We will always need a human to shuttle people to airports and drive food trucks coast to coast, obviously.
  • Banker. Nothing can beat the personal touch of a slender banker, all smiles and a nice suit, meeting you in a brick-and-mortar branch to tell you which buttons to push on your phone — the service courtesy of your account fees.
  • Electrician. So you can clean the vents in the data centers. If you are lucky, you get to install solar panels.

In 2008, when I was on the job market, computer science was at its nadir. The people behind the doors I was knocking on told me kids were told to study biology and law instead. What happened instead is that people entering the field precisely at that point were going to graduate at a very good time.

Mathematics of the impossible: book is done

Download the book here. As I tell my students, in research you don’t finish anything: you only begin. Indeed I plan to keep working on this book pretty much indefinitely, so keep sending comments; I will incorporate them in due course. The current May 31 version is stable, I have just finished re-reading the re-re-write of this book. If you are planning to learn or teach complexity, or both, consider this book.

I vividly remember the moment, about 3.5 years ago, when I pressed the first key. As they say, a journey of a thousand miles begins with a single step. Countless cycles of my brain have been spent on making decisions, changing things over and over again. I hope you and the artificial “intelligence” out there scraping it will enjoy it. It was a strange time to be writing a book. Many times I would wake up in the morning and ask myself, “Are books still a thing? Are people still writing them?” Apparently yes, so let’s proceed.

I was asked for a “hook” for the book and I was happy to come up with this, which summarizes why I wrote it:

An iconoclastic book that overhauls computational complexity theory, featuring recent breakthroughs, neglected gems, and simpler expositions of the classics.

More cool results about the complexity of distributions

In no particular order,

Byramji, Kane, Morris, and Ostuni proved an almost tight separation for adaptive vs non-adaptive sampling in the word model. Previous papers I blogged about earlier, see this and this prove weaker separations.

Another very cool work is the sampling lower bound for low-degree polynomials by Khodabandeh and Shinkar. They appear to be able to boost a non-trivial sampling lower bound to an exponential one using some type of sunflower result for polynomials.

P vs. NP animation

I’ve been playing with some ideas for a cover for my book, and I ended up making an animation about P vs. NP. It’s on my homepage (I can’t embed javascript here). Click on a nail and see what happens; you can also move the chain to create other configurations. I was looking for something which was connected to the math in the book, and also visually appealing (?), and also related to the grand challenges in complexity theory, and on top of all of this something related to the (somewhat unorthodox) viewpoints expressed in the book. Any comment or other suggestions for the book cover (or the book itself) always welcome!

Feedback requested for the complexity book “Mathematics of the impossible”

I have just completed a draft of the book. It is the March 4 version on my homepage. CLICK HERE TO DOWNLOAD. (If you downloaded already, check you don’t have the earlier version cached.) I would very much appreciate any feedback on the book, including suggestions on things to include, especially if they fit well and are not overly technical. Please feel completely free to suggest your own results.

After collecting feedback, I plan to do one more pass and then it’s off to the press, so speak now ;-)

Here is the table of contents in case you want to know what the book is about before downloading:

0 Introduction
0.1 Teasers
0.1.1 Computing with three bits of memory
0.1.2 Randomness and derandomization
0.1.3 Proofs and delegating computation
0.1.4 Changing base losing no time and no space
0.2 Notation
0.3 Contents and comparisons
0.4 How to use this book
0.5 Acknowledgments

1 Time
1.1 Word programs
1.2 Complexity classes
1.3 You don’t need much to have it all
1.4 Composing programs
1.5 Universal programs
1.6 The fastest algorithm for Factoring
1.7 On the word size
1.7.1 Factoring with large words
1.8 The grand challenge
1.8.1 Undecidability and diagonalization
1.8.2 The hierarchy of Time
1.9 Problems
1.10 Notes

2 Circuits
2.1 The grand challenge for circuits
2.2 Circuits vs. Time
2.3 Cosmological, non-asymptotic impossibility
2.4 Problems
2.5 Notes

3 Randomness
3.1 Error reduction for one-sided algorithm
3.2 Error reduction for BPTime
3.3 The power of randomness
3.3.1 Verifying matrix multiplication
3.3.2 Checking if a circuit represents zero
3.4 Does randomness really buy time?
3.5 The hierarchy of BPTime
3.6 Problems
3.7 Notes

4 Reductions
4.1 Types of reductions
4.2 Multiplication
4.3 3Sum
4.4 Satisfiability
4.4.1 3Sat to Clique
4.4.2 3Sat to Subset-Sum
4.4.3 3Sat to 3Color
4.4.4 More
4.5 Power hardness from SETH
4.6 Search problems
4.7 Gap-Sat: The PCP theorem
4.8 Problems
4.9 Notes

5 Nondeterminism
5.1 Nondeterministic computation
5.2 Completeness
5.3 From programs to 3Sat in quasi-linear time
5.3.1 Efficient sorting circuits
5.4 Power from completeness
5.4.1 Max-3Sat
5.4.2 NP is as easy as detecting unique solutions
5.5 Alternation
5.5.1 Does the hierarchy collapse?
5.6 Problems
5.7 Notes

6 Space
6.1 Branching programs
6.2 The power of L
6.2.1 Arithmetic
6.2.2 Graphs
6.2.3 Linear algebra
6.3 Checkpoints
6.4 The grand challenge for space
6.5 Randomness
6.6 Reductions
6.6.1 P vs. PSpace
6.6.2 L vs. P
6.7 Nondeterministic space
6.8 An impossibility result for 3Sat
6.9 TiSp
6.10 Computing with a full memory: Catalytic space
6.11 Problems
6.12 Notes

7 Depth
7.1 Depth vs space
7.2 The power of NC2: Linear algebra
7.3 Formulae
7.3.1 The grand challenge for formulae
7.4 The power of NC1: Arithmetic
7.5 Computing with 3 bits of memory
7.6 Group programs
7.7 The power NC0: Cryptography
7.8 Word circuits
7.8.1 Simulating circuits with square-root space
7.9 Uniformity
7.10 Problems
7.11 Notes

8 Majority
8.1 The power of TC0: Arithmetic
8.2 Neural networks
8.3 Amplifying lower bounds by means of self-reducibility
8.4 The power of Majority: Boosting correlation
8.5 Uniformity
8.6 Problems
8.7 Notes

9 Alternation
9.1 The polynomial method over F2
9.1.1 AC0 correlates with low-degree polynomials modulo 2
9.1.2 Using the correlation to show that Majority is hard
9.2 The polynomial method over R
9.2.1 AC0 correlates with low-degree real polynomials
9.2.2 Sign-Approximating Maj-AC0
9.2.3 Using the correlation to show impossibility for Maj-AC0
9.2.4 AC0 has small correlation with parity
9.3 Switching lemmas
9.3.1 Switching I
9.3.2 Switching II
9.3.3 Proof of switching II
9.4 AC0 vs L, NC1, and TC0
9.4.1 L
9.4.2 Linear-size log-depth
9.4.3 TC0
9.5 The power of AC0: Gap majority
9.5.1 Back to the PH
9.6 Mod 6
9.6.1 The power of ACC0
9.7 Impossibility results for ACC0
9.8 The power of AC0: sampling
9.9 Problems
9.10 Notes

10 Proofs
10.1 Static proofs
10.2 Zero-knowledge proofs
10.3 Interactive proofs
10.4 Delegating computation: Interactive proofs for muggles
10.4.1 Warm-up: Counting triangles
10.4.2 Delegating NC
10.5 Problems
10.6 Notes

11 Pseudorandomness
11.1 Basic PRGs
11.1.1 Local tests
11.1.2 Low-degree polynomials
11.1.3 Local tests, II
11.1.4 Local small bias
11.2 PH is a random low-degree polynomial
11.3 Pseudorandom generators from hard functions
11.3.1 Stretching correlation bounds: The bounded-intersection generator
11.3.2 Turning hardness into correlation bounds
11.3.3 Hard-core sets
11.3.4 Derandomizing the XOR lemma
11.3.5 Encoding the whole truth-table
11.3.6 Monotone amplification within NP
11.4 Finding the hard core
11.5 Cryptographic pseudorandom generators
11.5.1 AC0
11.5.2 Circuits
11.6 Problems
11.7 Notes

12 Expansion
12.1 Edge expansion
12.2 Spectral expansion
12.3 Undirected reachability in L
12.4 What do expanders fool?
12.5 On the proof of the PCP theorem
12.6 Problems
12.7 Notes

13 Communication
13.1 Two parties
13.1.1 The rectangle method and the Equality function
13.1.2 Rounds: Pointer chasing
13.1.3 Randomness
13.1.4 Arbitrary partition
13.2 Number-on-forehead
13.2.1 Generalized inner product
13.2.2 The power of logarithmic parties
13.2.3 Pointer chasing
13.3 Problems
13.4 Notes

14 Arithmetic
14.1 Linear transformations
14.1.1 The power of depth-2 xor circuits
14.2 Integers
14.3 Univariate polynomials
14.4 Multivariate polynomials
14.5 Depth reduction and completeness
14.6 Alternation
14.6.1 The power of depth 3
14.6.2 Impossibility results
14.7 Problems
14.8 Notes

15 Structures
15.1 Static
15.1.1 Succinct
15.1.2 Succincter
15.1.3 Impossibility results by ruling out samplers
15.2 Dynamic
15.3 Problems
15.4 Notes

16 Tapes
16.1 On the alphabet
16.1.1 The universal TM
16.2 Multi-tape machines
16.2.1 Time vs. TM-Time
16.3 TMs vs circuits
16.4 The grand challenge for TMs
16.4.1 Communication bottleneck: crossing sequences
16.5 TM-Time hierarchy
16.6 Randomness
16.7 Sub-logarithmic space
16.7.1 The power of sub-logarithmic space
16.8 Problems
16.9 Notes

17 Barriers
17.1 Black-box
17.2 Natural proofs
17.2.1 Examples of proofs that are natural
17.2.2 Ruling out natural proofs under popular conjectures
17.3 Problems
17.4 Notes

18 Speculation
18.1 Critique of common arguments for P ≠ NP

A Miscellanea
A.1 Logic
A.2 Integers
A.3 Sums
A.4 Inequalities
A.5 Probability theory
A.5.1 Deviation bounds for the sum of random variables
A.6 Squaring tricks
A.7 Duality
A.8 Groups
A.9 Fields
A.10 Linear algebra
A.11 Polynomials
A.12 Notes

A Landscape

Lust for life

I just finished reading the book. I savored it over months, reading just a few pages each day. There are many memorable passages I can relate to, for example about the need for the “artist’s illusion,” being alone painting in the country thinking of creating a masterpiece and ignoring that thousands of other canvases are painted every day, and the feeling that days are interminable, if you can’t paint all the time. And it was fun to read about something I knew nothing about, painting, coal miners, impressionism and the life of Vincent van Gogh. To think that I missed the exposition at the MFA right in front of my office, as well as the museum in Amsterdam…

I came to know about this book after someone pointed me to this memorial about Maryam Mirzakhani, according to which the book “exemplified her excitement about work and life in general.” I wish I had talked more to her when we crossed at Harvard.

Make schools safe again

Here’s an interesting piece on gun violence, worth reading.

These days I am playing a lot of Fortnite (I managed to get to gold in ranking, but naturally it’s a completely hopeless battle, plus I play with controller instead of mouse and keyboard). I have been thinking of two ways in which media promotes gun culture. The first one is the obvious realistic gore and splatter, dead bodies everywhere, well-known at least since the Iliad. The second is more sneaky, and that’s what’s used in Fortnite. You don’t show any blood, instead you mix war with emoji, toy weapons like slingshot, and general cartoony themes, so you get a teen rating, and familiarize everybody with the differences between a shotgun, an msg, an assault rifle in terms of ranges, reload times, and spread. You know, it might come in handy.

The Simpsons, S02E09 – “Itchy & Scratchy & Marge” has a hilarious exchange about the responsibility of media in violence. I can’t find the text online, but basically, the fact that there was violence before cartoons is put forth as a startling discovery which obviously invalidates any link between media and violence. Worth watching.