Wednesday, September 11, 2024

Natural Proofs is Not the Barrier You Think It Is

If there's a position where I differ from most other complexity theorists it's that I don't believe that natural proofs present a significant barrier to proving circuit results. I wrote about this before but I buried the lead and nobody noticed.

Let's review natural proofs. I'll give a very high-level description. Li-Yang Tan gives a good technical description or you could read the original Razborov-Rudich paper. A natural proof to prove lower bounds against a circuit class \(\cal C\) consists of a collection \(C_n\) of Boolean functions on \(n\) inputs such that

  1. No polynomial-size circuit family from \(\cal C\) can compute an element of \(C_n\) for large enough \(n\). 
  2. \(C_n\) is a large fraction of all the function on \(n\) inputs.
  3. A subset of \(C_n\) is constructive--given the truth-table of a function, you can determine whether it sits in the subset in time polynomial in the length of the truth-table. Note: This is a different than the usual notion of "constructive proof". 
The natural proof theorem states that if all three conditions hold than you can break pseudorandom generators and one-way functions.

My problem is with the third property, constructivity. I haven't seen good reasons why a proof should be constructive. When I saw Rudich give an early talk on the paper, he both had to change the definition of constructivity (allowing subsets instead of requiring an algorithm for \(C_n\) itself) and needed to give heavily modified proofs of old theorems to make them constructive. Nothing natural about it. Compare this to the often maligned relativization where most proofs in complexity relativize without any changes.

Even Razborov and Rudich acknowledge they don't have a good argument for constructivity.
We do not have any formal evidence for constructivity, but from experience it is plausible to say that we do not yet understand the mathematics of \(C_n\) outside exponential time (as a function of \(n\)) well enough to use them effectively in a combinatorial style proof.
Let's call a proof semi-natural if conditions (1) and (2) hold. If you have a semi-natural proof you get the following implication. 

Constructivity \(\Rightarrow\) One-way Functions Fail

In other words, you still get the lower bound, just with the caveat that if an algorithm exists for the property than an algorithm exists to break a one-way function. You still get the lower bound, but you are not breaking a one-way function, just showing that recognizing the proofs would be as hard as breaking one-way functions. An algorithm begets another algorithm. You don't have to determine constructivity either way to get the lower bound. 

Even if they aren't a great barrier to circuit lower bounds, natural proofs can be an interesting, if badly named, concept in their own right. For example the Carmosino-Impagliazzo-Kabanets-Kolokolova paper Learning Algorithms from Natural Proofs.

So if I don't believe in the barrier, why are circuit lower bounds hard? In recent years, we've seen the surprising power of neural nets which roughly correspond to the complexity class TC\(^0\), and we simply don't know how to prove lower bounds against powerful computational models. Blame our limited ability to understand computation, not a natural proof barrier that really isn't there.

Sunday, September 08, 2024

Very few problems are in NP intersect coNP but not known to be in P. What to make of that?

Someone once told me:

 I was not surprised when Linear Programming was in P since it was already in \(  NP \cap  coNP  \), and problems in that intersection tend to be in P.

The same thing happened for PRIMALITY.

However FACTORING, viewed as the set 

\( \{ (n,m) \colon \hbox{there is a factor of n that is } \le m \} \),

is in \(  {\rm NP} \cap {\rm coNP} \).  Is that indicative that FACTORING is in P? I do not think so, though that's backwards-since I already don't think FACTORING is in P, I don't think being in the intersection is indicative of being in P.

Same for DISCRETE LOG, viewed as the set

\( \{ (g,b,y,p) : \hbox{p  prime, g is a gen mod p and } (\exists x\le y)[ g^x\equiv b \pmod p] \} \) 

which is in \( {\rm NP} \cap {\rm coNP} \).

1) Sets in  \({\rm NP} \cap {\rm coNP}  \) but not known to be in P:

FACTORING- thought to not be in P, though number theory can surprise you.  

DISCRETE LOG-thought to not be in P, but again number theory...

PARITY GAMES-thought to not be in P. (See Lance's post on the theorem that PARITY GAMES are in Quasi-poly time see here.) 

Darn, only three that I know of. If  you know others, then let me know.

2) Candidates for sets in \( {\rm  NP} \cap {\rm coNP} \) but not known to be in P:

Graph Isomorphism. Its in NP and its in co-AM. Under the standard derandomization assumptions GI is in AM=NP so then GI would be in \( {\rm NP} \cap {\rm coNP} \). Not known to be in P. Is it in P? I do not think there is a consensus on this. 

Darn, only one that I know of. If you know of others, then let me know, but make sure they are not in the third category below. 

3) Problems with an \( {\rm NP} \cap  {\rm coNP} \) feel to them but not known to be in P.

A binary relation B(x,y) is in TFNP if,  B(x,y)\in P and, for all x there is a y such that

|y| is bounded by a poly in |x|

B(x,y) holds.

So these problems don't really fit into the set-framework of P and NP.

TFNP has the feel of \( {\rm NP} \cap  {\rm coNP} \).

Nash Eq is in TFNP and is not known to be in P, and indeed thought to not be in P. There are other problems in here as well, and some complexity classes, and some completeness results. But these problems are not sets so not in the intersection. (I will prob have a future post on those other classes.)

--------------------------

So what to make of this? Why are so few problems in the intersection? Does the intersection = P (I do not think so)?

---------------------------

I close with another quote: 

as a former recursion theorist I hope that  \(NP \cap coNP\)=P, but as someone whose credit card numbers are on the web, I hope not. 





Wednesday, September 04, 2024

Favorite Theorems: Parity Games

August Edition

A quasipolynomial-time algorithm for a long standing open problem. Yes, we have two of them this decade.

Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan

covered this theorem in 2017. In a parity game, Alice and Bob take turns walking along a directed graph with integer weights on the vertices and no sinks. Alice wins if the largest weight seen infinitely often is even. While it's not hard to show computing the winner sits in NP\(\cap\)co-NP and even UP\(\cap\)co-UP, the authors give the surprising result that you can determine the winner in near polynomial time.

The result has implications for modal logics, for example that model checking for the \(\mu\)-calculus can now be solved in quasipolynomial-time.

In follow-up work, Hugo Gimbert and Rasmus Ibsen-Jensen give a short proof of correctness of the parity games algorithm. Marcin Jurdziński and Ranko Lazić give an alternative algorithm that reduces the space complexity from quasipolynomial to nearly linear.

Sunday, September 01, 2024

Six degrees of separation has been proven. Really?

There is a paper (see here for an article about the paper, the link to the paper itself is later) that claims to PROVE that, on average, the distance (for some definition of distance) between any two people is 6.

1) We've blogged about this kind of thing:

My Pope Number is 2

What is your Erdos Number?

The six degrees of VDW

2) The paper's link is here and in case link rot sets in, my copy of it is here.

3) The paper has 14 authors. AH- so that's why we are, on the average, 6 degrees apart- because papers have so many authors. (Actually papers in Biology  have LOTS more than 14.)

4) The paper defines a mathematical model for social networks and analyzes a persons cost and benefit of forming a connection. 

5) Is the mathematical model realistic? I think so. But its always tricky since empirical evidence already gave the answer of six. The true test of a mathematical model is to predict something we didn't already know. 

6) One thing about applying this to the real world: What is a connection? Friendship? (also hard to define), handshakes? I like the will respond to my emails metric, though that may leave out half of my colleagues and even some of my friends.

(How come people do not respond to important emails? Perhaps a topic for a later blog.) 

7) My Jeopardy number is 1 in two different ways:

a)  My co-author Erik Demaine was mentioned in a question on Jeopardy, see here and look at the 800 dollar question in Double Jeopardy, Category Boy Genius.

b) My cousin Adam Winkler's book, Gunfight,  was mentioned in a question Jeopardy, see here. It was a 400 dollar question.

In both cases the question was easy, hence my inside information did not give me an advantage. 

(Note: they were actually mentioned in an answer on Jeop since Jeop has that weird format where they give the answer and you need to find the question. For example:

Game show that has a format that Bill Gasarch thinks is stupid

What is Jeopardy?

Thursday, August 29, 2024

My Quantum Summer

Rendering of PsiQuantum's facility in Chicago

I wasn't looking for quantum this summer but it found me. At various events I ran into some of the most recognized names in quantum computing: Peter Shor, Charlie Bennett, Gilles Brassard and Scott Aaronson (twice), Harry Buhrman and Ronald de Wolf.

I was invited to Amsterdam for a goodbye event for Harry Buhrman. Harry co-founded and co-led the CWI quantum center QuSoft and has now moved to London to join Quantinuum as chief scientist and I was invited to give a talk on Harry's classical complexity work before he joined the dark side. Ronald and Gilles gave talks after mine. 

On the way to Amsterdam I spent a few days visiting Rahul Santhanam in Oxford. Scott Aaronson and Dana Moshkovitz showed up with kids in tow. Scott gave a talk on AI not quantum in Oxford. I would see Scott again at the Complexity conference in Michigan.

Peter Shor and Charlie Bennett both attended the Levin Event I mentioned last week.

I talked to all of them about the future of quantum computing. Even though I'm the quantum skeptic in the crowd, we don't have that much disagreement. Everyone agreed we haven't yet achieved practical applications of quantum computing and that the power of quantum computing is often overstated, especially in what it can achieve for general search and optimization problems. There is some disagreement on when we'll get large scale quantum computers, say enough to factor large numbers. Scott and Harry would say growth will come quickly like we've seen in AI, others thought it would be more gradual. Meanwhile, machine learning continues to solve problems we were waiting for quantum machines to attack. 

My city of Chicago had a big quantum announcement, the Illinois Quantum and Microelectronics Park built on an old steel works site on the Southeast Side of the city built with federal, state and local funds as well as a big investment from PsiQuantum. I have my doubts as to whether this will lead to a practical quantum machine but no doubt having all this investment in quantum will bring more money and talent to the area, and we'll get a much better scientific and technological understanding of quantum. 

PsiQuantum's website claims they are "Building the world's first useful quantum computer". PsiQuantum is using photonic qubits, based on particles of light. Harry's company Quantinuum is using trapped ions. IBM and Google are trying superconducting qubits. Microsoft is using topological qubits and Intel with Silicon qubits (naturally). Who will succeed? They all might. None of them? Time will tell, though it might be a lot of time.

Monday, August 26, 2024

Whats worse for a company: being hacked or having technical difficulties? I would have thought being hacked but...

At the Trump-Musk interview:

1) There were technical difficulties which caused it to start late and have some other problems.

2) Musk and (I think) Trump claimed that this was a DDOS attack because people were trying to prevent Donald from having his say (listen to the beginning of the interview).

3) Experts have said it was not a DDOS attack, or any kind of attack.

(For the interview see here. If the link does not work either blame a DDOS hack or technical difficulties.)

When a company is hacked, to they admit it? This is hard to tell since if it never comes out, how do you know? 

Would a company rather admit to the public they had tech difficulties OR admit to the public they were attacked? I would think they would rather admit to the public they had tech difficulties. 

I suspect that X had tech difficulties because LOTS of people wanted to hear Trump.

Faced with this, what are Elon's options:

Options

1) Claim that this was caused because so many people wanted to hear Trump that the system could not handle it. This would make Trump look good, not make Elon look too bad, and is probably true so it won't be discovered later that he lied.

2) Claim that his system was attacked. This allows Trump to claim his enemies are out to get him, thus pushing the narrative that he is a victim. But Musk looks worse than if the system was just overloaded. Plus its false which will (and did) come out. However, there were absolutely no consequences to lying. 

I think its  unusual for a company to lie by claiming they were hacked when they weren't. If you know of any other examples then please comment.





Wednesday, August 21, 2024

The Levin Translation

Earlier this summer I attended a Celebration for Leonid Levin who recently turned 75. To prepare my talk I wanted to go back to Levin's 1971 two-page Russian masterpiece that covered both his independent discovery of NP-completeness and Universal Search. Boris Trakhtenbrot's wonderful Survey of Russian Approaches to Perebor has a messy translation of the Levin paper in the appendix. Could I use AI to get a cleaner version? TLDR Here's the PDF.

Let me first take a detour to when I was a graduate student in the 1980s. I went to meet my advisor Mike Sipser and found him with a couple of Russian students and postdocs carefully translating the latest paper from Alexander Razborov, then a young researcher at the Steklov Mathematical Institute in Moscow. Razborov had send a physical copy of his latest paper and they were translating word by word--would this be the paper that show NP sets don't have polynomial-size circuits and P ≠ NP? Spoiler alert: It wasn't, but the process remained etched in my memory four decades later.

But now we live in the 2020s and I turned to my friend Claude for help. I gave Claude the Russian PDF and asked Translate into English

Certainly, I'll translate the Russian text into English for you. Here's the translation:

PROBLEMS OF INFORMATION TRANSMISSION

Volume IX 1973 Issue 3

BRIEF COMMUNICATIONS

UDC 519.14

UNIVERSAL SEQUENTIAL SEARCH PROBLEMS

L. A. Levin

The article examines several well-known mass problems of the "sequential search type" and proves that these problems can only be solved in the time it takes to solve any problem of the specified type in general...

So far so good. Summarize the article.  

This article by L. A. Levin, titled "Universal Sequential Search Problems," discusses a class of computational problems known as "sequential search problems" or "enumeration problems." Here's a summary of the key points:

1. The article addresses well-known computational problems that require exhaustive search (enumeration) to solve.

2. While many classical problems have been proven to be algorithmically unsolvable, there exists a class of problems that are solvable but require an impractically large amount of computation time.

3. These problems, called "sequential search problems," include tasks like minimizing Boolean functions, searching for proofs of limited length, and determining graph isomorphism.

4. While these problems can be solved by simple algorithms that enumerate all possibilities, such algorithms require exponential time, leading mathematicians to believe that simpler algorithms are impossible.

5. The article introduces the concept of "universal sequential search problems" - problems to which all other sequential search problems can be reduced.

6. Levin presents six specific problems (numbered 1-6 in the text) and claims they are universal sequential search problems.

7. The main theorem (Theorem 1) states that if there exists any sequential search problem that cannot be solved in less than f(n) time (for some function f), then the six presented problems also cannot be solved in less than f(n) time.

8. Another important result (Theorem 2) states that for any sequential search problem, there exists an algorithm that solves it in optimal time, up to a constant factor and an additive term comparable to the input length.

9. The article suggests that this approach can be extended to most interesting sequential search problems.

10. While the article doesn't solve the fundamental question of whether these problems truly require exponential time, it establishes relationships between different problems in this class.

This work is significant in computational complexity theory, as it relates various hard problems to each other and suggests a hierarchy of difficulty among computational tasks.

The summary is almost as long as the article.

Then I noticed the term "mass problems" that occurs throughout the paper. In the translation the word "mass" seems off. What are some alternatives?

You're right to notice that the word "mass" in this context might seem unusual or potentially confusing. In the original Russian text, the term used is likely "массовые задачи" (massovye zadachi), which is a term commonly used in Russian mathematical literature. However, in English, we typically use different terminology. Here are some alternative translations that might be more appropriate in this context:

1. "General problems" or "general computational problems"

2. "Large-scale problems"

3. "Broad classes of problems"

4. "Universal problems"

5. "Widely applicable problems"

6. "Common computational problems"

7. "Algorithmic problems"

8. "Computational class problems"

9. "Generic problems"

10. "Generalized problems"

In the context of this paper, the author is likely referring to problems that are not specific to a particular instance but represent a whole class or type of problem. The term "universal" is actually used later in the paper, which aligns well with this interpretation.

So, a more idiomatic translation might replace phrases like "classical mass problems" with "classical universal problems" or "broad classes of classical problems".

This choice of wording would better convey the idea that these are problems that apply broadly across many instances or types of computational tasks, rather than being specific to a particular case.

So "mass problems" is mass as in mass audience not mass as in physics. What if we left out the word "mass" completely.

You're right, omitting the word "mass" entirely could indeed improve the clarity and flow of the translation without losing the essential meaning. Let's consider how some key sentences would read without it:

1. Instead of:

"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical mass problems was proven..."

We could have:

"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical problems was proven..."

2. Instead of:

"However, if we assume that there exists some (even artificially constructed) mass problem of the sequential search type that cannot be solved by simple algorithms..."

We could have:

"However, if we assume that there exists some (even artificially constructed) problem of the sequential search type that cannot be solved by simple algorithms..."

3. And for the theorem:

"If there exists any problem of sequential search (quasi-sequential search) type that cannot be solved in time less than f(n) for argument length comparable to n, then problems 1-6 also have this property."

This approach works well because:

1. The context already implies that we're dealing with broad classes of problems, not specific instances.

2. The term "sequential search problems" itself conveys the idea of a general class of problems.

3. It makes the text more concise and easier to read in English.

4. It avoids potential confusion that might arise from an unusual use of the word "mass" in this context.

So yes, simply omitting "mass" throughout the translation would likely result in a clearer, more idiomatic English text while preserving the original meaning of the article.

Give me the full translation without the mass, which Claude dutifully did. Why stick with a text version. Format this nicely in latex. 

Certainly! Here's the article formatted in LaTeX.

This LaTeX code will produce a nicely formatted version of the paper. It includes:

  1. Proper title, author, and abstract
  2. Sections for introduction, definitions and problems, and main results
  3. Theorem, lemma, and definition environments
  4. Proper mathematical formatting for equations and logical statements
  5. Enumerated list for the six problems
  6. Bibliography section

To compile this LaTeX document, you would need to save it as a .tex file and run it through a LaTeX compiler. The output will be a professionally formatted academic paper.

So I did and here is the final PDF

Russian papers at the time famously had no proofs so for fun I tried Can you fill in the proofs of the theorems

Certainly! I'll expand the LaTeX document to include proofs for the theorems and lemma. Please note that since the original paper doesn't provide detailed proofs, I'll have to construct plausible proofs based on the information given and general knowledge of the field. These proofs should be considered as educated guesses rather than the actual proofs from Levin's original work.

Here's the updated LaTeX code with added proofs.

This expanded version includes proof sketches for Theorem 1, Lemma 1, and Theorem 2. These proofs are constructed based on the information given in the paper and general principles of computational complexity theory. They should give a good idea of the reasoning behind the theorems, but may not exactly match Levin's original proofs.

The main ideas in these proofs are:

  1. For Theorem 1: Using the universality of problems 1-6 to show that they must be at least as hard as any other sequential search problem.
  2. For Lemma 1: Demonstrating how an arbitrary sequential search problem can be reduced to one of the listed problems (in this case, Problem 2).
  3. For Theorem 2: Constructing a universal algorithm that simulates all possible algorithms in parallel, achieving optimal time complexity up to a constant factor.

These proofs maintain the paper's focus on the relationships between different types of sequential search problems and the idea of universal sequential search problems.

You can judge the proofs on your own. 

Sunday, August 18, 2024

Request open problems in honor of Luca Trevisan

 Request for Open Problems In Memory of Luca Trevisan


Luca Trevisan passed away on June 19, 2024 at the age of 52, of cancer.

I am putting together an open problems column of open problems in his honor.

If you are interested in contributing then please email me a document with the following specifications.

1) It can be as short as half-a-page or as long as 2 pages. One way to make it short is to give many references or pointers to papers with more information.

2) It should be about an open problem that is either by Luca or inspired by Luca or a problem you think Luca would care about.

3) In LaTeX. Keep it simple as I will be cutting-and-pasting all of these into one column.

Deadline is Oct 1, 2024.