Sign In

Communications of the ACM

Blogroll



From Gödel's Lost Letter and P=NP

Diophantine Equations

Complexity of solving polynomial equations [ Jeff ] Jeff Lagarias is a mathematician or a professor at the University of Michigan. Today I wish to discuss Diophantine...

From Gödel's Lost Letter and P=NP

How To Make A Polynomial Map Nicer

Stability theory and polynomials [ Essen ] Arno van den Essen is the author of the book on the Jacobian Conjecture. Today I want to highlight one of the ideas he...

From Gödel's Lost Letter and P=NP

Raymond Edward Miller Just Passed Away

Miller just passed away at 90 [ GIT ] Ray Miller just passed away. He had been a researcher and leader at IBM Research, Georgia Tech, and University of Maryland...

From Gödel's Lost Letter and P=NP

A Rank Problem

More on restricted quantum circuits [ The Daily Grail ] Ken Regan just wrote about his paper with Chaowen Guan (GR). The paper is titled, “Stabilizer Circuits,...

From Gödel's Lost Letter and P=NP

Selected Papers at CCC 2019

Some papers from the accepted list of this year’s Computational Complexity Conference [ UB CSE ] Alan Selman is a long-time friend of Ken and I, and is a long-time...

From Gödel's Lost Letter and P=NP

Making Up Tests

It’s harder to make up tests than to take them [ Recent photo ] Ken Regan has been busy these last few days working on making a final exam, giving the exam, and...

From Gödel's Lost Letter and P=NP

An App Proof

That is “app” as in an on-line application [ Leo Stein ] Leo Stein is an assistant professor in the department of Physics and Astronomy at the University of Mississippi...

From Gödel's Lost Letter and P=NP

Internet, Dogs, and the ABC Conjecture

An inappropriate comment on the ABC conjecture Joseph Oesterlé and David Masser are famous for their independent discovery of the ABC conjecture. Today I want to...

From Gödel's Lost Letter and P=NP

Making Elections Safe

A new proof that MAJORITY is not in . [ Rich DeMillo ] Rich DeMillo is a strong leader, a famous researcher, and a long-time best friend. Proof: He was the first...

From Gödel's Lost Letter and P=NP

The Network Coding Conjecture Is Powerful

More hard Boolean functions Peyman Afshani, Casper Freksen, Lior Kamma, and Kasper Larsen (AFKL) have a recent paper which we just discussed. Today Ken and I will...

From Gödel's Lost Letter and P=NP

Sedgewick Wins An Award

An award for educational writing [ ACM ] Robert Sedgewick is the 2018 recipient of the ACM Outstanding Educator Award. Today we congratulate Bob on this wonderful...

From Gödel's Lost Letter and P=NP

Network Coding Yields Lower Bounds

Practice leads theory Peyman Afshani, Casper Freksen, Lior Kamma, and Kasper Larsen have a beautiful new paper titled “Lower Bounds for Multiplication via Network...

From Gödel's Lost Letter and P=NP

Why Check A Proof?

Why check another’s proof? [Russell and Whitehead ] Bertrand Russell and Alfred Whitehead were not primarily trying to mechanize mathematics in writing their famous...

From Gödel's Lost Letter and P=NP

P=NP Proofs

Advice to claimers The Claimers The Claimers are a gang on the hit AMC television series The Walking Dead. They are the main antagonists in the second half of the...

From Gödel's Lost Letter and P=NP

A Reason Why Circuit Lower Bounds Are Hard

And a possible approach to avoid this obstacle Valentine Kabanets is a famous complexity theorist from Simon Fraser University. He has been at the forefront of...

From Gödel's Lost Letter and P=NP

Seeing Is Believing

Introducing a notion that captures information flow [ Her own hall ] Anita Jones is, of course, a famous computer scientist, a famous Carnegie Mellon University...

From Gödel's Lost Letter and P=NP

Avi Wins The Knuth Prize

Wigderson wins the well deserved Knuth Prize From Avi’s 60Fest at IAS Avi Wigderson is this year’s selection for the ACM/IEEE Donald E. Knuth Prize. Today Ken and...

From Gödel's Lost Letter and P=NP

The Breakthrough Result Of 2019

Our nomination for best result of the year Cropped from source Faadosly Polir has had an incredible year of research success. A year ago we covered his research...

From Gödel's Lost Letter and P=NP

The Shortest Path To The Abel Prize

While melding topology, geometry, and analysis IAS page Karen Uhlenbeck is a mathematician who has won a number of awards in the past and has just now been announced...

From Gödel's Lost Letter and P=NP

Leprechauns Go Universal

Facing nonexistential realities Neil L. is a Leprechaun. He has graced these pages before. Today, the day before St. Patrick’s Day, we ponder universal riddles...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account