POSTED UPDATED VERSION OF Computers and Intractability: A guide to Algorithmic Lower Bounds posted (New title)

We have posted a revised version of 

Computational Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi

The book is here.

(For the original post about it, edited it to use the new title (see below), see HERE.) 

We  changed the title (the title above is the new one) 

since the earlier title looked too much

like the title of Garey's and Johnson's classic. While that was intentional we 

later felt that it was too close to their title and might cause confusion. 

Of course changing the title might also cause confusion; however, 

this post (and we will email various people as well) will stem that confusion. 

We welcome corrections, suggestions and comments on the book. Email us at hardness-book@mit.edu

There are two different definitions of Integer Programming. Why?

Alice and Bob have the following conversation.

===============================

ALICE: In your book you define INT PROG as, given a matrix A and vectors b,c,

find the integer vector x such that Ax\le b and c DOT x is maximized.

This is not correct! You also need x\ge 0.

BOB: Really? I always heard it without that extra constraint, though I am

sure they are equivalent and both NP-complete (Alice nods).

Where did you see it defined with that extra constraint?

ALICE:

Wikipedia entry in IP

Chapter of a book at an MIT website

Something on Science Direct

A course at Duke

An article by Papadimitriou 

An article on arxiv

The book Graphs, Networks and Algorithms by Dieter Jungnickel

Bob, do you have examples where they do not use that extra constraint. 

BOB: 

Math Works

Lecture notes from UIUC

Lecture notes from Lehigh Univ.

The book Parameterized Complexity Theory by Flum and Grohe

The book Computers and Intractability : A Guide to the Theory of NP-Completeness by Garey and Johnson

ALICE: Both of our lists are impressive. So now what? 

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

(This is Bill again.)

What indeed!

1) Why are there two definitions of Int Prog?

2) When is it good to use which one? 

Monarachy: A Problem with Definitions

 As I am sure you know, Queen Elizabeth II passed away at the age of 96 recently.  I am not a royal-watcher, but I am a royal-watcher-watcher. That is, the question of why people care about the lives of these people intrigues me. A few notes

1) Was she a good Queen? People tend to think so; however, since the job is somewhat ill-defined its hard to say. 

2) The Queen is supposed to be above politics (she does not vote- I was surprised to find out that legally she can, but she really can't). We know very few of Queen Elizabeth II's opinions on political events. But the notion of political is not well defined. One would think that if she did an appeal for people to take the COVID vax that would not be political, but somehow it is (I do not know if she did such an appeal). King Charles III believes in global warming and that we need to do something about it. This again should not be political but is. 

3) She is the second longest reigning Monarch. First is King Louis XIV who first became king at the age of 4. I had a blog complaining about this here. However, there is a more interesting point I want to make. From the first to the last day of King Louis XIV reign not much had changed. Technology, politics, other things just didn't change much. By contrast the world changed A LOT between Queen Elizabeth II first and last day:

a) The British were an important power in 1952. Less so now.

b) When her father died she was in Kenya and it took 4 hours to get the news to her. Now that would be immediate. 

c) Divorce was considered bad in 1952 and is why King Edmond VIII could not be king (he wanted to marry a twice-divorced woman whose ex-husbands were still alive). And now three of the Queen's children have been divorced.

d) Gay people.. enough said. There has even been a royal gay wedding, see here

Black people (can't call them African-Americans), Women,... you fill it in. 

e) When Charles wanted to get married it seemed to be important that he marry a virgin. We cannot imagine this mentality anymore. When Prince William and Kate got married they were already living together and this was NOT an issue for ANYONE. I looked up what the Church of England thought of it and all I got was some very bland comments like That's what young people do nowadays. 

3) Is the monarchy a good thing? As an American I feel I do not have a right to an opinion. If the citizens of the United Kingdom approve of the monarch (polls show they do) then who am I do tell them they are wrong? Even so, lets look at reasons for it

a) Tourism. It has been said that the Monarchy leads to MONEY from tourism. So it is worth the price? Nobody seems to know and it would be hard to tell. However, I don't think the citizens of the United Kingdom view  money as the reason for Monarchy. The American analog is giving Disneyland tax breaks to be in Florida which generates jobs. I doubt they think of the Monarchy in those mundane transactional terms. 

b) CS Lewis said 

Where men are forbidden to honour a king they honour millionaires, athletes, or film stars instead: even famous prostitutes and gangsters. For spiritual nature, like bodily nature, will be served; deny it food and it will gobble poison.

This is  bit odd- they must all pretend to like the monarchy to make it work. A long time ago when Charles and Dianna were both having affairs, 80% of the citizens the United Kingdom thought that was okay so long as they are discreet so the people don't find out. But- those ARE the people.

Also odd- CS Lewis was a theologian and a  believing Christian; however, his comment above can apply to God as well as to Kings. 

Thirty Years of Dagstuhl

 

Dagstuhl old-timers at the original castle

I'm back at Dagstuhl for the seminar on Algebraic and Analytic Methods in Computational Complexity. My first seminar at Dagstuhl was back in 1992. I've been coming for thirty years and have been here roughly thirty times. My last trip was pre-covid (virtual Dagstuhls don't count) and I really needed this chance to hang out and talk complexity with colleagues old and new.

Some changes since my last trip. The room doors have locks (there are rumors of an incident). You have to create your own keycard on a new machine logging into your Dagstuhl account. I had a long random password through a password manager and it was not so easy as process.

The main conference room has been updated with tech for hybrid meetings, and new led lights. Books were removed from the library to create a coffee breakout space.

No Bill this time so no typecasts. Still the best part of the week is talking and hearing about complexity. Today I learned about the orientations of Sperner's lemma, that there is one more triangle oriented according to the direction of the corner vertices than those oriented the other way. Christian Ikenmeyer used this fact to motivate a study of closure properties of #P-functions.

The NIST Process for Post-Quantum Cryptography

Guest post by Jonathan Katz

Over the past few months there have been several interesting developments in the NIST post-quantum standardization process.

By way of background, since the advent of Shor's algorithm in 1994 we have known that a large-scale, general-purpose quantum computer would be able to break all currently deployed public-key cryptography in (quantum) polynomial time. While estimates vary as to when (or even whether!) quantum computers will become a realistic threat to existing public-key cryptosystems, it seems prudent to already begin developing/deploying newer "post-quantum" schemes that are plausibly secure against quantum computers.

With the above in mind, NIST initiated an open process in 2017 for designing post-quantum cryptographic standards. Researchers from around the world submitted candidate algorithms for public-key encryption/key exchange and digital signatures. These were winnowed down over a series of rounds as cryptographers publicly debated the relative merits of different proposals, or showed security weaknesses in some candidates.

On July 5 of this year, NIST announced that it had selected four of the submissions as finalists for standardization. Only one candidate for public-key encryption was chosen, along with three digital signature schemes. Three of the four selected algorithms rely on the hardness of lattice problems; the only non-lattice scheme is a hash-based signature scheme. (It is possible to build digital signatures using "symmetric-key" assumptions alone.) In addition, four other public-key encryption schemes not based on lattices were designated for further study and possible standardization at a later point in time.

Less than one month later, Castryck and Decru announced a classical attack on SIKE, one of the public-key encryption schemes chosen for further study. SIKE is based on a conjectured hard problem related to isogenies on supersingular elliptic curves. The attack was not just theoretical; the researchers were able to implement the attack and run it in less than a day or less, depending on the security level being considered. Details of the attack are quite complex, but Galbraith gives a high-level overview. Subsequent improvements to the attack followed.

It is worth adding that the above follows an entirely classical attack shown roughly six months earlier on Rainbow, another submission to the NIST standardization process that made it to the 3rd round. (Rainbow is a signature scheme that relies on an entirely different mathematical problem than SIKE.) For completeness, note that none of the four finalists are impacted by any of these attacks.

A few reflections on the above:

• It is amazing that the factoring and RSA problems are still hard (for classical computers), more than 40 used after they were proposed for cryptography. The same goes for the discrete-logarithm problem (in certain groups).
• It is not easy to find other hard mathematical problems! Code-based cryptography has been around about as long as factoring, but has been somewhat unpopular for reasons of efficiency. Lattice-based cryptosystems still seem to give the leading candidates.
• We need more (non-cryptographers) studying cryptographic assumptions. The attacks on SIKE involved deep mathematics; attacks on lattice problems may involve algorithmic ideas that cryptographers haven't thought of.

Computational Intractability: A Guide to Algorithmic Lower Bounds. First draft available! Comments Welcome!

(This post is written by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi)

In 1979 Garey and Johnson published the classic

        Computers and  Intractability: A Guide to NP-Completeness

There has been A LOT of work on lower bounds since then.

Topics that were unknown in 1979 include

Parameterized Complexity,

 Lower bounds on approximation,

Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), 

Online Algorithms,

Streaming Algorithms, 

Polynomial Parity Arguments, 

Parallelism, and 

Many new problems have been shown complete or hard in NP, PSPACE, and other classes.

Hence a sequel is needed. While it is impossible for one book to encompass all, or even a large fraction, of the work since then, we are proud to announce a book that covers some of that material:

Computational Intractability: A Guide to Algorithmic Lower Bounds

by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi. MIT Press. 2024

See HERE for a link to a first draft.

We welcome corrections, suggestions and comments on the book. Either leave a comment on this blog post or emailing us at hardness-book@mit.edu

20 Years of the Computational Complexity Weblog

I first posted on this blog twenty years ago today, still the oldest and longest running weblog in theoretical computer science, possibly in all of computer science. In those twenty years we've had nearly 3000 posts and over 23,000 comments and 10,000,000 page views. Bill Gasarch joined me officially as a co-blogger over 15 years ago on March 30, 2007. 

We've seen major results in computational complexity but the biggest challenges remain, in particular major separations of complexity classes. We've also had a front row seat to a computing revolution with  the growth of cloud and mobile computing, social networks connecting us for better or for worse, and incredible successes of machine learning. It's almost as though we've been handed an oracle that gives us much of the goodness of P = NP while leaving cryptography intact. 

What will the next twenty years bring? We'll be watching, posting and tweeting. Hope you keep reading and commenting. 

Conference Modality

We have had an almost normal summer conference season, for some sense of normal. At one of those conferences I participated in an hybrid conversation about whether the conference should be in-person, virtual or hybrid the following year. Here are some general thoughts.

In-Person

The traditional conference format. People travel from near and far to a hotel, conference center or campus location. Talks given in large rooms, often in parallel. A reception, some social activities, participants gathering in small groups to go out for meals. 

Positives: In-person maximizes interaction between participants. Being physically away from your home means you can focus your time on the conference and your fellow participants. This was more true before the mobile devices/laptops/internet days, but still most participants will spend more time on-site than on-line.

Negatives: Expensive--with registration, hotel and air fare, even a domestic participant could have to pay $2000 or up, higher for those traveling internationally. Visas can be hard to get. Some still feel unsafe in large groups. People often leave early, pity the last speakers. And don't forget the carbon footprint. 

As countries declare war on other countries or states deny certain rights, there is a push against meetings in certain places. Note the disclaimer for next year's FCRC. You might upset some people if you have conferences at these locations (and others if you don't).

Virtual

Virtual conferences would never in the past have been taken seriously but Covid forced our hands. 

Talks are streamed or pre-recorded. Some interaction with chats in talks, zoom get togethers or though a systems like virtual chair. Even if we had a perfect "metaverse" experience where we could get together as though we were in person, not being there in person means we wouldn't make it a priority.

The big advantages are costs are low, it's easy to attend talks, and no danger of spreading disease. Still a virtual conference can feel too much like just a collection of streamed and recorded talks.

Hybrid

So let's make the conference hybrid and have the best of both worlds. Alas, it doesn't work out that way. It's nearly impossible to have good interaction between in-person and virtual participants--basically you have to run two separate meetings. Do you allow virtual talks or require an author to show up in person. 

How do you set prices? Lower prices for virtual increases assess but decreases in-person attendance. Participants (or their advisors) might opt to save expenses and attend virtually instead of in-person, reducing the networking opportunities for everyone. 

Most conferences tend to take the hybrid route to avoid the complaints if one went fully in-person or virtual, but hybrid just pretty much guarantees a mediocre experience for all.

Opinion

My suggestion is some years run the conference virtually and others in hybrid. We already have too many conferences, a byproduct of our field using conferences as the primary publication venue. I suggest following conferences like the International Congress of Mathematicians or the Game Theory World Congress, held every four years. If the main conference of a field is held every four years, researchers, particularly senior researchers, make a bigger effort to be there. You can have the virtual meetings the other years so researchers, particularly students, can continue to present their work.

No easy solutions and CS conferences have not worked well for years. Maybe the struggle to define future conferences will allow us to focus more on the connecting researchers than just "journals that meet in a hotel".