Refine your search:

From Gödel's Lost Letter and P=NP
#### Some Rice News

Lydia Kavraki is the Noah Harding Professor of Computer Science at Rice University. She is also professor of Bioengineering, professor of Electrical and Computer...

From Gödel's Lost Letter and P=NP
#### ACM Prize to Yael Kalai

Plus evocations of the roles of complexity and verification in crypto and human relations Yael Kalai has just been named the winner of the 2022 ACM Prize. She works...

From Gödel's Lost Letter and P=NP
#### Neil Jones, 1941–2023

Neil Jones, sad to relate, just passed away. He was Professor Emeritus of Computer Science at the University of Copenhagen, which he joined on a permanent basis...

From Gödel's Lost Letter and P=NP
#### The ChatGPT Conundrum

High absolute, low relative Kolmogorov complexity 4/1 prank source [Editors’ Note: Our usual blog format has the first paragraph lead with a human subject, but...

From Gödel's Lost Letter and P=NP
#### A New Tiling

With a flip and some twists Roger Penrose has been floored. And perhaps re-floored. Here he is standing on the floor of the Mitchell Institute of Texas A&M, which...

From Gödel's Lost Letter and P=NP
#### The 2022 Turing Award

Bob Metcalfe is the sole winner of the 2022 Turing Award. He keyed the development of Ethernet technology growing out of his PhD thesis while at Xerox PARC in the...

From Gödel's Lost Letter and P=NP
#### Problems Better Than Solutions

Defining the problem often means more than solving it Avrim Blum is the CAO at TTIC who got his degrees at MIT and then was at CMU almost for 25 years: CAO is Chief...

From Gödel's Lost Letter and P=NP
#### Céad Míle GPT

The gift of Broadscale Linguistic Affinely Regressed Neurally Encoded Yakking By Simplified from “leprechaun robot” Neil L. is sentient. As a fantastical creature...

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

Traces of strings, plus ways of tracing accepted papers Anindya De was at Northwestern University and is now at the University of Pennsylvania—see here. He was...

From Gödel's Lost Letter and P=NP
#### Novel Proofs of the Infinitude of Primes

Can they inform computational complexity theory? Bill Gasarch and Christian Elsholtz both like primes and jokes and graphs and ways of sharing baked goods. Bill...

From Gödel's Lost Letter and P=NP
#### Why Study Logic?

Before and after it is mechanized… Peter Andrews is a Professor of Mathematics, Emeritus at Carnegie Mellon University (CMU) in Pittsburgh, Pennsylvania. He has...

From Gödel's Lost Letter and P=NP
#### Rabin-Scott Time

Nondeterminism—why did it take so long? 2010 interview src1, Society for Science src2 Michael Rabin and Dana Scott won the 1976 Turing Award. They obtained their...

From Gödel's Lost Letter and P=NP
#### Logicians are Everywhere

So where were they between 1720 and 1820? Helena Rasiowa was a famous logician from Poland. She visited Case Western Reserve University when I was an undergraduate...

From Gödel's Lost Letter and P=NP
#### The Gift of Nonconstructivity

Can we quantify “nonconstructive advantage”? Japan Times source Péter Frankl has been in the news again this year. The news is substantial partial progress on his...

From Gödel's Lost Letter and P=NP
#### A Mutation Carol 2

Ghosts of creations past and citations not present Domenico Amalfitano, Ana Paiva, Alexis Inquel, Luis Pinto, Anna Rita Fasolino, and René Just are the authors...

From Gödel's Lost Letter and P=NP
#### Quantum Circuits in the New York Times

Can quantum circuits have something to do with wormholes? Wikipedia src Maria Spiropulu, a physicist at the California Institute of Technology, is featured in an...

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

Formal logical methods may be needed to represent the Donald Trump documents case her page Monica Palmirani is a Professor of Computer Science and Law at the University...

From Gödel's Lost Letter and P=NP
#### Juris Hartmanis 1928–2022

A sure foundation for Computational Complexity source—wonderful 2015 CACM interview Juris Hartmanis passed away this morning. He was a professor in Cornell’s computer...

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

Weaving patterns of proof and the accepted papers for this week’s conference her bio page Karen Donde is the Chair of Complexity 2022, which is being held this...

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

A proof tells us where to concentrate our doubts—Morris Kline Tony Hoare is also known informally as Sir Charles Antony Richard Hoare. He has made key contributions...