Embracing the Future of Manufacturing

Last week I walked around the International Manufacturing Technology Show with 89,000 other participants at the McCormick Center in Chicago. I went to see how AI was affecting manufacturing and it wasn't quite the way I was expecting.

The sheer scale of physical machinery is overwhelming: from elaborate manufacturing equipment and numerous robots, to water jets performing precision cuts on metal. You also notice the international aspects--the big booths belonged to German, Japanese and Taiwanese companies, not so much American. US leads the world in many things, but manufacturing technology is not one of them.

There was one exception--the three big cloud providers: Google, Microsoft and AWS (Amazon). All, especially Microsoft, have dedicated cloud services for manufacturing. All were touting their AI services for manufacturing from predictive maintenance to Edge AI to generative AI diagnosing machine failures. It was less clear if the audience was listening.

When I walked around a Health Tech show last year, one could fee the focus on data and the excitement about AI even just a few months after ChatGPT went public. At IMTS the feeling was different. The most exciting "new technology" was allowing supervisors to get stats and adjust the machines remotely from the beach, offering retrofits to old machines to allow it to happen. One exhibitor showed me an app where a line worker could show a video to a distant supervisor to get some help (they need a new app for that?). I suggested that soon the supervisor could be replaced by AI in the app and they gave me a funny look.

The most interesting use of AI came from a small Oregon-based company Machine Research, which uses AI for small manufacturers to create bids from proposals. It's a small operations--just seven employees, basically only two developers working on the cloud. 

Like academia, the manufacturing industry is slow to change. Replacing old machines and products are expensive--you can't just do a software update. Both presidential candidates are pushing to increase manufacturing in the US but unless we can take advantage of our technical strengths, embracing the future and Industry 4.0, we'll find it hard to compete. Tariffs and financial incentives will only take us so far.

How will chatGPT affect Homework?

LANCE: I gave my final exam for my ugrad theory course (regular, Context Free, P, NP, Decidable, Undecidable) to the new ChatGPT o1 that claims to reason about math to see how it would do.

BILL: How did it do?

LANCE: Impressive--beat most of my students. Lets just say I could write a pretty good letter of recommendation.

BILL (arrogantly): I am a great problem maker, so this won't affect me. I ask problems in Grad Ramsey that ChatGPT would crash and burn on.

LANCE:  Okay big-shot, email me some HWs from Ramsey and we'll see how ChatGPT does on it.

BILL: Okay! 

[Bill emails Lance the first two HW assignments and prediction on how ChatGPT will do.

Bill predicts that it will do well on the standard problems, but crash and burn on unusual problems that (key!) are not on the web. Concepts that Bill invented just for his course. Bill is mostly correct in these predictions.]

LANCE: But how did Chatty do compared to the students who took the course?

BILL: About the same with one caveat: when ChatGPT gets something wrong its really weird- it has the look and feel of a proof but what it outputs is something no human would ever right. So it does badly on getting partial credit. And one other thing- asking it to do a proof A CERTAIN WAY or SIMILAR TO WHAT I DID IN CLASS it does badly on.

LANCE: I wonder if the same holds for Ramsey courses taught at other universities. Wait is there even any one else who teaches Ramsey theory?

BILL: Very funny. In your theory course I  assume students can't use ChatGPT on an exam so this is not really a problem. But for HW it might be a problem. It also brings up the analog of the question

do we allow students to use slide rules on an exam

LANCE: Slide rules? Your age is showing.

BILL: I am only 2 years older than you. Or is it 3? I forget these things.

LANCE: Yes, I would allow students to use ChatGPT as long as they acknowledge they did so, write up their own solution and take responsibility for any mistakes. Problem is they will just cut and past.

BILL: Lets break this down course-by-course

GRAD RAMSEY:  The students want to be there and are very good. My hope is that 

1) For standard problems they won't need ChatGPT

2) For unusual problems ChatGPT won't help. And I am good at making up unusual problems.

3) In any case, if they use it and they UNDERSTAND the answer and put it into their own words, I am okay with that.

HONORS DISCRETE MATH: Similar to Ramsey though I am a bit nervous.

UNDERGRAD THEORY  (similar to Lance's course): I would like to think its similar to Ramsey Theory.  However, I may be wrong.

ALL COURSES:

There is a more profound problem here that applies to all courses: the students may confuse getting the answer from ChatGPT with understanding. 

LANCE: ChatGPT is a hell of a lot better at solving problems than it was last week. Maybe ChatGPT won't help on the unusual problems today but that might not last for long. Perhaps the solution is to just give up on assessments and stop grading all together. Students can learn if they want to and waste their money if they don't.

BILL: That kind of change in how we educate is above my pay grade. You are a Dean, so it may be at your pay grade.

LANCE: Nope, even deans have their limits.

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 large 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.

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. 

Favorite Theorems: Parity Games

August Edition

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

Deciding Parity Games in Quasi-polynomial Time

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

I 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.

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?

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.

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.