Gödel's Lost Letter and P=NP

new theory

My dear wife, Kathryn Farley, just woke me this Friday the 20th from a nap with something that she said was amazing.

She told me it was the top most viewed video of the entire day—over a million views. It was indeed terrific—especially for a video by women who work in complexity theory.

A Result From Simons

As part of their flashback series, they are sharing one of the most popular videos from our SimonsTV YouTube channel. In May 2020, the Women in Theory conference, which was scheduled to take place at the Simons Institute, was held online due to coronavirus restrictions. In connection with the event, the group released a video of a special theoretical—computer-science version of Gloria Gaynor’s classic song “I Will Survive”.

See it here with new lyrics by Avi Wigderson.

Today this video was indeed the top most watched one of the day. It beat out a president candidate singing about cats and dogs—see here. And is much cooler.

This Sunday’s NYTimes had an article on Eliyahu Rips who just just passed away at 75. He was an Israeli mathematician known for his research in geometric group theory. He had became known to the general public years ago following his co-authoring a paper on what is popularly known as Bible code, the supposed coded messaging in the Hebrew text of the Torah.

The book by Michael Drosnin claimed that historical and future events were encoded in the Old Testament, although he couldn’t explain how or why.

Find Secrets in Public Documents

Drosnin began researching the Bible Code in 1992 after meeting the mathematician Eliyahu Rips in Israel. His work was deeply inspired by the publication of the academic article entitled

Equidistant Letter Sequences in the Book of Genesis by Doron Witztum, Eliyahu Rips, and Yoav Rosenberg in the journal Statistical Science, published by the Institute of Mathematical Statistics, in August 1994.

He had also become convinced that statistical tools and newer, more powerful computers that were becoming available in the 1980s could be used to identify hidden meaning within the Bible, and he teamed up with his two partners to discover them. Their biggest finding was the names of 32 Jewish scholars in the text, along with their birth or death dates; several of the scholars had lived thousands of years after Genesis was written.

Open Problems

The idea is to have a document D that is public. Then they run some search that finds some object S that is encoded inside D. This is suppose to show that D is more interesting than we previously thought. The object S is not obviously hidden in D—this is the whole point.

There is an old Jewish tradition about a “hidden text” in the Hebrew Pentateuch (the Five Books of Moses), consisting of words or phrases expressed in the form of equidistant letter sequences (ELS’s) — that is by selecting sequences of equally spaced letters in the text. Since this tradition was passed orally, only few expressions that belong to the “hidden text” were preserved in writing (Rabbenu Bahya, 1492 and Cordovero, 1592); actually almost all the words and the syntax are unknown. Rabbi H.M.D. Weissmandel (Weissmandel, 1958) was the first to try to show the existence of such a “hidden text”, by finding interesting patterns consisting of ELS’s.

Santosh Vempala is the chair of this FOCS 2024 conference. Here is the schedule of the talks. And in our next section are the accepted papers with links so you can see the results now.

His committee is:

Daniel Alabi, Columbia

Nima Anari, Stanford

Maryam Aliakbarpour, Rice

Xiaotie Deng, Peking University

Jelena Diakonikolas, Wisconsin

Alina Ene, BU

Funda Ergun, Indiana

Vipul Goyal, NTT Research

Sean Hallgren, Penn State

Russell Impagliazzo, UCSD

Varun Kanade, Oxford

Ravi Kannan, CMU

Bhavana Kanukurthi, IISc

Lap Chi Lau, Waterloo

Francois Le Gall, Nagoya

Andrea Lincoln, BU

Yang P. Liu, IAS and CMU

Daniel Lokshtanov, UCSB

Meena Mahajan, IMSc

Yury Makarychev, TTIC

Tal Malkin, Columbia

Dana Moshkovitz, UT Austin

Anand Natarajan, MIT

Alantha Newman, CNRS

Noam Nisan, Hebrew University

Huy Nguyen, Northeastern

Rafail Ostrovsky, UCLA

Ioannis Panageas, UC Irvine

Will Perkins, Georgia Tech

Prasad Raghavendra, Berkeley

Victor Reis, IAS

Rahul Santhanam, Oxford

Mohit Singh, Georgia Tech

Daniel Stefankovic, Rochester

David Steurer, ETH

Xiaorui Sun, UIC

Ewin Tang, Berkeley

Kavitha Telikepalli, TIFR Mumbai

Vera Traub, Bonn

Chris Umans, Caltech

Vinod Vaikuntanathan, MIT

Adrian Vetta, McGill

Yusu Wang, UCSD

Andre Wibisono, Yale

Mihalis Yannakakis, Columbia

Huacheng Yu, Princeton

Accepted Papers

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
Tolson Bell, Alan Frieze (Carnegie Mellon University)

A stronger bound for linear 3-LCC
Tal Yankovitz (Tel Aviv University)

Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
Zeyu Guo (The Ohio State University); Chaoping Xing, Chen Yuan (Shanghai Jiao Tong University); Zihan Zhang (The Ohio State University)

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
Sasank Mouli (Mahindra University)

Capacity Threshold for the Ising Perceptron
Brice Huang (MIT)

{Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
Marcelo Garlet Milani (National Institute of Informatics, Tokyo, Japan); Stephan Kreutzer (TU Berlin); Irene Muzi (Universitaet Hamburg); Meike Hatzel (National Institute of Informatics, Tokyo, Japan)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Yang Liu (IAS)

Online Combinatorial Allocations and Auctions with Few Samples
Paul Duetting (Google); Thomas Kesselheim (University of Bonn); Brendan Lucier (Microsoft Research); Rebecca Reiffenhauser (University of Amsterdam); Sahil Singla (Georgia Tech)

Efficient approximate unitary designs from random Pauli rotations
Jeongwan Haah (Microsoft Quantum); Yunchao Liu (UC Berkeley); Xinyu Tan (MIT)

Verifying Groups in Linear Time
Ohad Klein (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research); Shai Evra, Shay Gadot (Hebrew University)

Fast list decoding of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal (Chennai Mathematical Institute); Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar (Tata Institute of Fundamental Research)

First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier (TU Wien); Ioannis Eleftheriadis (University of Cambridge); Nikolas Mahlmann (University of Bremen); Rose McCarty (Georgia Institute of Technology); Micha Pilipczuk, Szymon Toruczyk (University of Warsaw)

Proofs of Space with Maximal Hardness
Leonid Reyzin (Boston University)

A Dense Model Theorem for the Boolean Slice
Gil Kalai, Noam Lifshitz, Tamar Ziegler (Hebrew University of Jerusalem); Dor Minzer (MIT)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand (Georgia Tech); Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans (ETH Zurich); Maximilian Probst Gutenberg (ETH Zurich); Sushant Sachdeva (University of Toronto / Google)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Carnegie Mellon University); Prasad Raghavendra (U.C. Berkeley)

Power Series Composition in Near-Linear Time
Yasunori Kinoshita (Tokyo Institute of Technology); Baitian Li (Tsinghua University)

The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
Zhiyan Ding (University of California, Berkeley); Ethan N. Epperly (Caltech); Lin Lin (University of California, Berkeley); Ruizhe Zhang (Simons Institute for the Theory of Computing)

Obstructions to Erdos—Posa Dualities for Minors
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos (LIRMM, Univ. Montpellier, CNRS, France); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, South Korea)

Optimal Bounds for Open Addressing Without Reordering
Martin Farach-Colton (NYU); Andrew Krapivin (Rutgers University); William Kuszmaul (Harvard University)

Tight Bounds for Classical Open Addressing
Michael Bender (Stony Brook University); William Kuszmaul (Harvard University); Renfei Zhou (Tsinghua University)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)

Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
Shiri Ron (Weizmann Institute of Science); Clayton Thomas (Microsoft Research); S. Matthew Weinberg, Qianfan Zhang (Princeton University)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math \& CSAIL, MIT); Ewin Tang (UC Berkeley)

Structure learning of Hamiltonians from real-time evolution
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math \& CSAIL, MIT); Ewin Tang (UC Berkeley)

Gaussian Approximation of Convex Sets by Intersections of Halfspaces
Anindya De (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)

Constant Degree Direct Product Testers with Small Soundness
Mitali Bafna (MIT); Noam Lifshitz (Hebrew University); Dor Minzer (MIT)

On Approximating Cutwidth and Pathwidth
Nikhil Bansal (University of Michigan); Dor Katzelnick (Technion —Israel Institute of Technology); Roy Schwartz (Technion)

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler (ETHZ \& Carnegie Mellon University); Richard Hladik, Vaclav Rozhon (ETH Zurich); Robert Tarjan (Princeton University); Jakub T?tek (BARC, University of Copenhagen)

Gapped Clique Homology is QMA1-hard and contained in QMA
Robbie King (Caltech); Tamara Kohler (Stanford)

Boosting uniformity in quasirandom groups: faster and simpler
Emanuele Viola (NEU); Harm Derksern (Northeatern University); Chin Ho Lee (NCSU)

The sample complexity of smooth boosting and the tightness of the hardcore theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan (Stanford University)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Omar Alrabiah, Venkatesan Guruswami (UC Berkeley)

Reverse Mathematics of Complexity Lower Bounds
Lijie Chen (University of California at Berkeley); Jiatu Li (Massachusetts Institute of Technology); Igor C. Oliveira (University of Warwick)

Agnostically Learning Multi-index Models with Queries
Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Vasilis Kontonis (University of Texas-Austin); Christos Tzamos, Nikos Zarifis (University of Wisconsin-Madison)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan (MIT); Vaclav Rozho (ETH Zurich); Jakub Ttek, Mikkel Thorup (University of Copenhagen)

Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
Sayan Bhattacharya (University of Warwick); Din Carmon (Tel Aviv University); Martin Costa (University of Warwick); Shay Solomon, Tianyi Zhang (Tel Aviv University)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilo (University of LAquila); Shiri Chechik (Tel-Aviv University); Keerti Choudhary (Indian Institute of Technology); Sarel Cohen (The Academic College of Tel Aviv-Yaffo, Israel); Tobias Friedrich (Hasso Plattner Institute); Martin Schirneck (University of Vienna, Austria)

An Improved Line-Point Low-Degree Test
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi (Tata Institute of Fundamental Research); Madhu Sudan (Harvard University)

Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Yaonan Jin (Huawei TCS Lab); Pinyan Lu (Shanghai University of Finance and Economics)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
Sayan Bhattacharya, Martin Costa (University of Warwick); Naveen Garg (IIT Delhi); Silvio Lattanzi, Nikos Parotsidis (Google Research)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Robert Andrews, Avi Wigderson (Institute for Advanced Study)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time
Bernhard Haeupler (ETH Zurich \& Carnegie Mellon University); Yaowei Long, Thatchaphol Saranurak (University of Michigan)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics)

The Tractability Border of Reachability in Simple Vector Addition Systems with States
Dmitry Chistikov (Centre for Discrete Mathematics and its Applications (DIMAP) \& Department of Computer Science, University of Warwick, Coventry, UK); Wojciech Czerwiski, ukasz Orlikowski, Filip Mazowiecki (University of Warsaw); Henry Sinclair-Banks (Centre for Discrete Mathematics and its Applications (DIMAP) \& Department of Computer Science, University of Warwick, Coventry, UK); Karol W?grzycki (Saarland University and Max Planck Institute for Informatics, Saarbrucken, Germany)

Semi-Bandit Learning for Monotone Stochastic Optimization
Arpit Agarwal (Columbia University); Rohan Ghuge (Georgia Institute of Technology); Viswanath Nagarajan (University of Michigan)

Sparse graph counting and Kelley—Meka bounds for binary systems
Yuval Filmus (Technion—Israel Institute of Technology); Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Esty Kelman (MIT, Boston University)

Replicability in High Dimensional Statistics
Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye (University of California, San Diego)

Efficient Unitary Designs from Random Sums and Permutations
Chi-Fang Chen (Caltech); Jordan Docter, Michelle Xu, Adam Bouland (Stanford); Fernando Brandao (Caltech); Patrick Hayden (Stanford)

Commitments are equivalent to one-way state generators
Rishabh Batra (CQT); Rahul Jain (National University of Singapore)

On the Existence of Seedless Condensers: Exploring the Terrain
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach (Cornell University)

Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)

Nearly Optimal List Labeling
Michael A. Bender (Stony Brook University); Alex Conway (Cornell Tech); Martin Farach-Colton, Hanna Komlos (New York University); Michal Koucky (Charles University); William Kuszmaul (Harvard University); Michael Saks (Rutgers University)

Quantum eigenvalue processing
Guang Hao Low (Microsoft Research); Yuan Su (Microsoft)

Quantum computational advantage with constant-temperature Gibbs sampling
Thiago Bergamaschi (UC Berkeley); Chi-Fang Chen (Caltech); Yunchao Liu (UC Berkeley)

Towards Instance-Optimal Euclidean Spanners
Hung Le (University of Massachusetts Amherst); Shay Solomon (Tel Aviv University); Cuong Than (University of Massachusetts Amherst); Csaba D. Toth (California State University Northridge and Tufts University); Tianyi Zhang (Tel Aviv University)

Stochastic Online Correlated Selection
Ziyun Chen (Tsinghua University); Zhiyi Huang, Enze Sun (The University of Hong Kong)

Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
Lunjia Hu (Stanford University); Yifan Wu (Northwestern University)

Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger (ETH Zurich); Alexander Poremba (MIT); Makrand Sinha (UIUC); Henry Yuen (Columbia University)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Noah Golowich (MIT); Ankur Moitra (Math \& CSAIL, MIT); Dhruv Rohatgi (MIT)

Optimal tradeoffs for estimating Pauli observables
Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye (Tsinghua University)

Dot-Product Proofs and Their Applications
Nir Bitansky (New York University and Tel Aviv University); Prahladh Harsha (Tata Institute of Fundamental Research); Yuval Ishai, Ron Rothblum (Technion); David J. Wu (UT Austin)

Fast Mixing in Sparse Random Ising Models
Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, Madhu Sudan (Harvard University)

Efficient Certificates of Anti-Concentration Beyond Gaussians
Ainesh Bakshi (MIT); Pravesh Kothari (Princeton University and IAS); Goutham Rajendran (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Aravindan Vijayaraghavan (Northwestern University)

Minor Containment and Disjoint Paths in almost-linear time
Tuukka Korhonen (University of Bergen); Micha? Pilipczuk, Giann?s Stamoulis (University of Warsaw)

Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems
Hiroshi Hirai (Graduate School of Mathematics, Nagoya University); Keiya Sakabe (Graduate School of Information Science and Technology, The University of Tokyo)

A Sampling Lovasz Local Lemma for Large Domain Sizes
Chunyang Wang, Yitong Yin (Nanjing University)

Naively Sorting Evolving Data is Optimal and Robust
George Giakkoupis (INRIA); Marcos Kiwi (U. Chile); Dimitrios Los (University of Cambridge)

Tight Bounds for Sorting Under Partial Information
Ivor van der Hoog (Technical University of Denmark); Daniel Rutschmann (Technical University of Denmark, DTU)

Revisiting Agnostic PAC Learning
Steve Hanneke (Purdue University); Kasper Green Larsen (Aarhus University); Nikita Zhivotovskiy (UC Berkeley)

Computing the 3-edge-connected components of directed graphs in linear time
Evangelos Kosinas (ISTA (Institute of Science and Technology Austria)); Loukas Georgiadis (University of Ioannina); Giuseppe F. Italiano (LUISS University of Rome)

Decoding Quasi-Cyclic Quantum LDPC Codes
Louis Golowich, Venkatesan Guruswami (UC Berkeley)

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
Mikkel Abrahamsen, Jack Stade (University of Copenhagen, Denmark)

Semirandom Planted Clique and the Restricted Isometry Property
Jarosaw Basiok, Rares-Darius Buhai (ETH Zurich); Pravesh K Kothari (Princeton University and IAS); David Steurer (ETH Zurich)

A Lossless Deamortization for Dynamic Greedy Set Cover
Shay Solomon, Amitai Uzrad, Tianyi Zhang (Tel Aviv University)

Ramsey Theorems for Trees and a General Private Learning Implies Online Learning Theorem
Simone Fioravanti (Gran Sasso Science Institute); Steve Hanneke (Purdue University); Shay Moran, Hilla Schefler, Iska Tsubari (Technion)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
Yotam Dikstein (IAS); Irit Dinur (Weizmann Institute of Science); Alexander Lubotzky (Weizmann)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
Jarosaw Byrka (University of Wrocaw); Fabrizio Grandoni (IDSIA, University of Lugano); Vera Traub (University of Bonn)

Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders
Yotam Dikstein (IAS); Max Hopkins (UCSD)

Three-edge-coloring projective planar cubic graphs:\\ A generalization of the Four Color Theorem
Yuta Inoue (The University of Tokyo); Kenichi Kawarabayashi (National Institute of Informatics and The University of Tokyo); Atsuyuki Miyashita (The University of Tokyo); Bojan Mohar (Simon Fraser University); Tomohiro Sonobe (National Institute of Informatics)

Interactive Proofs for General Distribution Properties
Tal Herman (Weizmann Institute); Guy Rothblum (Apple)

Tight Bounds for the Zig-Zag Product
Gil Cohen, Gal Maor, Itay Cohen (Tel Aviv University)

Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications
Shuichi Hirahara (National Institute of Informatics); Zhenjian Lu (University of Warwick); Mikito Nanashima (Tokyo Institute of Technology)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal (University of Michigan); Vincent Cohen-Addad (Google Research, France); Milind Prabhu (University of Michigan); David Saulpic (Universite Paris Cite, CNRS); Chris Schwiegelshohn (Aarhus University)

The Online Submodular Assignment Problem
Sherry Sarkar, Daniel Hathcock, Mik Zlatin (Carnegie Mellon University); Billy Jin (Cornell University); Kalen Patton (Georgia Tech)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Pravesh K. Kothari (Princeton University and IAS); Peter Manohar (Carnegie Mellon University)

Efficient Approximation of Hypertree Width
Vaishali Surianarayanan (University of California Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Vika Korchemna (TU Wien)

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Jiatu Li, Edward Pyne (MIT); Roei Tell (University of Toronto)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
Aaron Bernstein (Rutgers University); Joakim Blikstad (KTH Royal Institute of Technology \& Max Planck Institute for Informatics); Thatchaphol Saranurak (University of Michigan); Ta-Wei Tu (Stanford University)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Friedrich Eisenbrand (EPFL); Lars Rohwedder (Maastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)

The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds
Ryan Williams (MIT)

Trading Determinism for Noncommutativity in Edmonds Problem
Arvind (Institute of Mathematical Sciences (HBNI), and CMI); Abhranil Chatterjee (Indian Statistical Institute, Kolkata); Partha Mukhopadhyay (Chennai Mathematical Institute)

Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Sushrut Karmalkar (UW-Madison); Shuo Pang (University of Copenhagen); Aaron Potechin (UChicago)

$\Pi_2^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
Dmitriy Zhuk (Charles University, Prague)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Renato Ferreira Pinto Jr. (University of Waterloo)

On Robustness to k-wise Independence of Optimal Bayesian Mechanisms
Nick Gravin, Zhiqi Wang (Shanghai University of Finance and Economics)

Expansion of high-dimensional cubical complexes with application to quantum locally Testable codes
Irit Dinur (Weizmann); Ting-Chun Lin (UCSD); Thomas Vidick (Weizmann Institute of Science)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

A computational test of quantum contextuality, and even simpler proofs of quantumness
Atul Singh Arora (University of Maryland, Caltech); Andrea Coladangelo (University of Washington); Alexandru Cojocaru (University of Edinburgh, University of Maryland); Kishor Bharti (A*STAR Quantum Innovation Centre (Q.InC), Institute of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR), Singapore. Centre for Quantum Engineering, Research and Education, TCG CREST, India.)

On Pigeonhole Principles and Ramsey in TFNP
Siddhartha Jain, Jiawei Li (UT Austin); Robert Robere (McGill); Zhiyang Xun (UT Austin)

New investigations into noncommutative CSPs
Eric Culf (University of Waterloo); Hamoon Mousavi (University of California at Berkeley); Taro Spirig (University of Copenhagen)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Moise Blanchard (MIT)

Strong vs. Weak Range Avoidance and the Linear Ordering Principle
Oliver Korten, Toniann Pitassi (Columbia University)

Novel properties of hierarchical probabilistic partitions and their algorithmic applications
Sandip Banerjee (IDSIA, USI-SUPSI, Lugano, Switzerland); Yair Bartal (Heberew University); Lee-Ad Gottlieb (Ariel University); Alon Hovav (Hebrew University)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Michal Opler (Czech Technical University, Prague)

Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger (ETH Zurich); Anand Natarajan, Tina Zhang (MIT)

An XOR Lemma for Deterministic Communication Complexity
Siddharth Iyer, Anup Rao (University of Washington)

Certifying almost all quantum states with few single-qubit measurements
Hsin-Yuan Huang (Google Quantum AI, Caltech); John Preskill (Caltech, AWS Center for Quantum Computing); Mehdi Soleimanifar (Caltech)

Locally Stationary Distributions
Kuikui Liu, Sidhanth Mohanty (MIT); Prasad Raghavendra (UC Berkeley); Amit Rajaraman (MIT); David X Wu (UC Berkeley)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Xifan Yu, Dmitriy Kunisky (Yale University)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
Krishnamurthy (Dj) Dvijotham (Google DeepMind); H. Brendan McMahan (Google); Krishna Pillutla (IIT Madras); Thomas Steinke, Abhradeep Guha Thakurta (Google DeepMind)

The Communication Complexity of Approximating Matrix Rank
Alexander A. Sherstov, Andrey A. Storozhenko (University of California, Los Angeles)

Jump operators, Interactive Proofs and Proof Complexity Generators
Erfan Khaniki (Institute of math of the CAS)

Optimal quantile estimation: beyond the comparison model
Mihir Singhal, Meghal Gupta, Hongxun Wu (UC Berkeley)

New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler (ETH Zurich \& CMU); D Ellis Hershkowitz (Brown University); Zihan Tan (DIMACS, Rutgers)

Tensor cumulants for statistical inference on invariant distributions
Dmitriy Kunisky (Yale University); Cristopher Moore (Santa Fe Institute); Alex Wein (UC Davis)

Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians
Jane Lee, Anay Mehrotra, Manolis Zampetakis (Yale University)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A\&M University)

Fully Dynamic Matching and Ordered Ruzsa—Szemeredi Graphs
Soheil Behnezhad, Alma Ghafari (Northeastern University)

Faster isomorphism testing of p-groups of Frattini class-2
Gabor Ivanyos (Institute for Computer Science and Control, Eotvos Lorand Research Network (ELKH), Budapest, Hungary); Euan Jacob Mendoza (University of Technology Sydney); Youming Qiao (Center for Quantum Software and Information, University of Technology, Ultimo NSW 2007, Australia); Xiaorui Sun (University of Illinois at Chicago); Chuanqi Zhang (University of Technology Sydney)

Spectral Guarantees for Adversarial Streaming PCA
Zhiyang Xun, Eric Price (The University of Texas at Austin)

Open Problems

I have always loved the FOCS conference. Hope that you can be there this October. I hope also to be there too.

Math problems get solved from time to time. Today I wonder if they are solved the way we guessed they were going to be solved? For example do most feel that P vs NP is likely to be equal or unequal?

William Gasarch has conducted three polls of researchers concerning this question. Confidence that P is not equal NP has been increasing: In 2002 61% believe unequal; in 2012 83% believe unequal; and in 2019 88% believed unequal. When restricted to experts, the 2019 answers became 99% believed unequal.

Many Are Guessed Right Before Being Solved

Consider the famous: 4 color theorem.It states that no more than four colors are required to color the regions of any planar map so that no two adjacent regions have the same color. Most seemed to believe that 4 colors was going to be enough.

False disproofs usually violated the assumptions of the theorem. Such as using a region that consists of multiple disconnected parts, or disallowing regions of the same color from touching at a point. They got the statement of the theorem incorrect. Martin Gardner (1975) played an April Fool’s joke by asserting that the McGregor map consisting of 110 regions required five colors and constitutes a counterexample to the four-color theorem.

Some Guessed Wrong Before Being Solved

The famous Fermat Last Theorem was that there was no positive integer solution to:
x^n + y^n = z^n
with n >2 and xyz not zero.

The link occurred by contemplating the unthinkable—what would happen if Fermat’s Last Theorem was not true? This would mean that there existed a set of solutions to Fermat’s equation, and therefore this hypothetical combination of numbers could be used as the basis for constructing a hypothetical elliptic curve. Ribet demonstrated that this elliptic curve could not possibly be related to a modular form, and as such it would defy the Shimura-Taniyama conjecture.

Running the argument backwards, if somebody could prove the Shimura-Taniyama conjecture then every elliptic curve must be related to a modular form, hence any solution to Fermat’s equation is forbidden to exist, and hence Fermat’s Theorem must be true. If somebody could prove the Shimura-Taniyama conjecture, then this would immediately imply the proof of Fermat’s Last Theorem. By proving one of the most important conjectures of the twentieth century, mathematicians could solve a riddle from the seventeenth century.

Open Problems

Here are two open problems that are not clear which way we should guess. The first is the Riemann Hypothesis and the second is the twin prime conjecture.

For the Riemann Hypothesis we could guess all the zeroes have real part 1/2. But it is not clear if all believe that this is likely to be the case. The twin prime could be the case that there are infinitely many primes p so that p+2 is also prime. But this might be false as some believe?

The Fulkerson prize is given to: outstanding papers in the area of discrete mathematics and is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of \$1,500 each are presented at each (triennial) International Symposium of the MOS.

This year:

* Ben Cousins and Santosh Vempala for Gaussian cooling and $O^{*}(n^{3})$ algorithms for volume and Gaussian volume.

* Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao for Equiangular lines with a fixed angle.

* Nathan Keller and Noam Lifshitz for The junta method for hypergraphs and the Erdos—Chvatal simplex conjecture.

Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson (1924-1976) to encourage mathematical excellence in the fields of research exemplified by his work.

Previous Prizes

1979:

* Richard M. Karp for classifying many important NP-complete problems.

* Kenneth Appel and Wolfgang Haken for the four color theorem.

* Paul Seymour for generalizing the max-flow min-cut theorem to matroids.

1982:

* D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grotschel, Laszlo Lovasz and Alexander Schrijver for the ellipsoid method in linear programming and combinatorial optimization.

* G. P. Egorychev and D. I. Falikman for proving van der Waerden’s conjecture that the matrix with all entries equal has the smallest permanent of any doubly stochastic matrix.

1985:

* Jozsef Beck for tight bounds on the discrepancy of arithmetic progressions.

* H. W. Lenstra Jr. for using the geometry of numbers to solve integer programs with few variables in time polynomial in the number of constraints.

* Eugene M. Luks for a polynomial time graph isomorphism algorithm for graphs of bounded maximum degree.

1988:

* Eva Tardos for finding minimum cost circulations in strongly polynomial time.

* Narendra Karmarkar for Karmarkar’s algorithm for linear programming.

1991:

* Martin E. Dyer, Alan M. Frieze and Ravindran Kannan for random-walk-based approximation algorithms for the volume of convex bodies.

* Alfred Lehman for 0,1-matrix analogues of the theory of perfect graphs.

* Nikolai E. Mnev for Mnev’s universality theorem, that every semialgebraic set is equivalent to the space of realizations of an oriented matroid.

1994:

* Louis Billera for finding bases of piecewise-polynomial function spaces over triangulations of space.

* Gil Kalai for making progress on the Hirsch conjecture by proving subexponential bounds on the diameter of d-dimensional polytopes with n facets.

* Neil Robertson, Paul Seymour and Robin Thomas for the six-color case of Hadwiger’s conjecture.

1997:

* Jeong Han Kim for finding the asymptotic growth rate of the Ramsey numbers R(3,t).

2000:

* Michel X. Goemans and David P. Williamson for approximation algorithms based on semidefinite programming.

* Michele Conforti, Gerard Cornuejols, and M. R. Rao for recognizing balanced 0-1 matrices in polynomial time.

2003:

* J. F. Geelen, A. M. H. Gerards and A. Kapoor for the GF(4) case of Rota’s conjecture on matroid minors.

*Bertrand Guenin for a forbidden minor characterization of the weakly bipartite graphs (graphs whose bipartite subgraph polytope is 0-1).

*Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and Alexander Schrijver for showing submodular minimization to be strongly polynomial.

2006:

* Manindra Agrawal, Neeraj Kayal and Nitin Saxena, for the AKS primality test.

* Mark Jerrum, Alistair Sinclair and Eric Vigoda, for approximating the permanent.

* Neil Robertson and Paul Seymour, for the Robertson—Seymour theorem showing that graph minors form a well-quasi-ordering.

2009:

* Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for the strong perfect graph theorem.

* Daniel A. Spielman and Shang-Hua Teng, for smoothed analysis of linear programming algorithms.

* Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture on the densest possible sphere packings.

2012:

* Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving the approximation ratio for graph separators and related problems

* Anders Johansson, Jeff Kahn, and Van H. Vu for determining the threshold of edge density above which a random graph can be covered by disjoint copies of a given smaller graph.

* Laszlo Lovasz and Balazs Szegedy for characterizing subgraph multiplicity in sequences of dense graphs.

2015:

* Francisco Santos Leal for a counter-example of the Hirsch conjecture.

2018:

* Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Bottcher for The chromatic thresholds of graphs

* Thomas Rothvoss for his work on the extension complexity of the matching polytope.

2021:

* Bela Csaba, Daniela Kuhn, Allan Lo, Deryk Osthus, and Andrew Treglown for Proof of the 1-factorization and Hamilton decomposition conjectures.

* Jin-Yi Cai and Xi Chen for Complexity of Counting CSP with Complex Weights.

*Ken-Ichi Kawarabayashi and Mikkel Thorup for Deterministic Edge Connectivity in Near-Linear Time.

Open Problems

Congrats to Ben and Santosh again. Wonderful.

Professors Yin Tat Lee and Thomas Rothvoss are faculty at the Allen School of the University of Washington.

Lee has the A.W. Tucker Prize that recognizes the best doctoral thesis in optimization in the past three years. Rothvoss, who holds a dual appointment in the Allen School and the Department of Mathematics, earned the Delbert Ray Fulkerson Prize recognizing outstanding papers in the area of discrete mathematics. They are advising theory PhD students in the Allen School—some jointly.

Paul Beame and Anna Karlin are some of the top senior theorists in the Allen School that I have known for many years.

Sally
One of the students in the theory group is Sally Dong who is a final year PhD student. I ran across her work recently the other day
here. She is working with Lee and Rothvoss.

Sally’s Paper

Computing Circle Packing Representations of Planar Graphs by Sally Dong, Yin Tat Lee, Kent Quanrud. See it here:

The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Primal-Dual Circle Packing Theorem for 3-connected planar graphs. The existence of these representations has widespread applications in theoretical computer science and mathematics; however, the algorithmic aspect has received relatively little attention. In this work, we present an algorithm based on convex optimization for computing a primal-dual circle packing representation of maximal planar graphs, i.e. triangulations. This in turn gives an algorithm for computing a circle packing representation of any planar graph. Both take the O(nlog(R/s)) expected run-time to produce a solution that is s close to a true representation, where R is the ratio between the maximum and minimum circle radius in the true representation.

Open Problems

I loved the fact that the Circle Packing Theorem was related to an ancient theorem of mine—with Bob Tarjan—on planar graphs. Dong’s paper says:

It gives a geometric proof of the Planar Separator Theorem of Lipton and Tarjan; an analysis of circle packing properties further gives an improved constant bound for the separator size; it is also used crucially to design a simple spectral algorithm for computing optimal separators in graphs of bounded genus and degree.

I loved that it could be used to prove better bounds on the size of the separators. Very cool.

Foundations of Computer Science 2024 is coming this fall: October 27-30, 2024 at Wolf Point Plaza, Chicago.

A Bit of History

The cover of the FOCS proceedings is:

It was designed by Alvy Ray Smith—many years ago.

See his comments here.

I was asked by my colleagues at the IBM Watson Research Center to design the cover of the 14th annual Switching and Automata Theory Symposium (SWAT), held in 1973. I did so one miserable night to escape the depression of an automobile failure in the worst part of the Bronx, in a rundown Esso station, in a snow storm. This design came to me, all at once, from thinking on the themes “cellular automata as models of living things”, “artificial intelligence”, and “self-reproducing machines”. However, it took me a month to execute the design, with Rapidograph, triangle, French curves, Exacto knife, and ellipse templates, in drafting ink on vellum – obviously before I discovered computer graphics.

FOCS 2024

The chair of the this FOCS is Santosh Vempala of Georgia Institute of Technology and the Program Committee is:

Daniel Alabi
Nima Anari
Maryam Aliakbarpour
Xiaotie Deng
Jelena Diakonikolas
Alina Ene
Funda Ergun
Vipul Goyal
Sean Hallgren
Russell Impagliazzo
Varun Kanade
Ravi Kannan
Bhavana Kanukurthi
Chi Lau
Le Gall
Nagoya Andrea
Yang P. Liu
Daniel Lokshtanov
Meena Mahajan
Yury Makarychev
Tal Malkin
Dana Moshkovitz
Anand Natarajan
Alantha Newman
Noam Nisan
Huy Nguyen
Rafail Ostrovsky
Ioannis Panageas
Will Perkins
Prasad Raghavendra
Victor Reis
Rahul Santhanam
Mohit Singh
Daniel Stefankovic
David Steurer
Xiaorui Sun
Ewin Tang
Kavitha Telikepalli
Vera Traub
Chris Umans
Vinod Vaikuntanathan
Adrian Vetta
Yusu Wang
Andre Wibisono
Mihalis Yannakakis
Huacheng Yu

Papers

Here are all the FOCS 2024 Accepted Papers. Below are just those accepted papers that are directly connected to Tech.

8. Online Combinatorial Allocations and Auctions with Few Samples by
Paul Duetting (Google); Thomas Kesselheim (University of Bonn); Brendan Lucier (Microsoft Research); Rebecca Reiffenhauser (University of Amsterdam); Sahil Singla (Georgia Tech)

12. First-Order Model Checking on Monadically Stable Graph Classes by
Jan Dreier (TU Wien); Ioannis Eleftheriadis (University of Cambridge); Nikolas Mahlmann (University of Bremen); Rose McCarty (Georgia Tech); Micha Pilipczuk, Szymon Toruczyk (University of Warsaw)

15. Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality by
Jan van den Brand (Georgia Tech); Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans (ETH Zurich); Maximilian Probst Gutenberg (ETH Zurich); Sushant Sachdeva (University of Toronto / Google)

48. Semi-Bandit Learning for Monotone Stochastic Optimization} by
Arpit Agarwal (Columbia University); Rohan Ghuge (Georgia Tech); Viswanath Nagarajan (University of Michigan)

81. Sampling, counting, and large deviations for triangle-free graphs near the critical density by Matthew Jenssen (King’s College London); Will Perkins (Georgia Tech); Aditya Potukuchi (York University); Michael Simkin (MIT)

90. Online Submodular Assignment Problem by Sherry Sarkar, Daniel Hathcock, Mik Zlatin (Carnegie Mellon University); Billy Jin (Cornell University); Kalen Patton (Georgia Tech)

Open Problems

Hope to see you all there. The conference should be wonderful as always.

Sadly Gordon Bell died May 17 at the age of 89, see this.

Bell died in Coronado, California from pneumonia. He was a true visionary in the world of computing who helped design some of the first minicomputers in the 1960s. Much will be written about his life and legacy, but his technical contributions were primarily in computer and system architecture. His impact on algorithms and theory are significant but may be less widely known.

Today Rich DeMillo and I wish to add to his memories from our own personal viewpoint. Rich especially interacted with Bell over the years and we hope he will add to the thanks that everyone has. This is mostly from his point of view.

Rich: Like many computer scientists whose careers began in the late 1960’s, my contact with Gordon was episodic. He was already a towering figure by the time Dick and I graduated. Some of us were more directly affected by his formidable presence than others. Dick was a graduate student at CMU, and, since Gordon deliberately blurred the line between DEC and CMU, he would have been steeped in the culture that promoted by Bell, Perlis, Simon, and Traub. Coincidentally, Perlis would also be an influence on both of us. Link to the GLL post on Social Processes. When I at NSF in the research directorate that founded, virtually everything I touched somehow reflected his view of that computational science should drive computing research, his work had a profound impact on supercomputer development when I was at HP because his high performance systems at DEC were acquired by HP in the Compaq merger.

DEC-CMU-DEC

Bell was working at the Speech Processing Lab at MIT at around the same time that Digital Equipment Corporation (DEC) was spun out of MIT Lincoln Labs by Ken Olson and Harlan Anderson, and joined DEC as the company’s first engineer. in 1960. His creation of the PDP-1 (Programmed Data Processor-1) line of minicomputers (computers of the time were expensive and enormous) instantly transformed data centers. The PDP line was mostly commercially successful, especially the later PDP-8 and PDP-10 machines which were ubiquitous in academic computer science and technical computing labs. The failed PDP-6 was an exception, but the PDP-10 used the same architecture with silicon semiconductors and was twice as fast. DEC dropped the price and sold 1,500 of these machines. After the launch of the Bell resigned form DEC after a disagreement with Olson, and joined the new academic computer science department at Carnegie Mellon University (CMU) here}.

From 1966 to 1972 Gordon was a professor of computer science and electrical engineering. He was perhaps the first to conceive computer architecture as a separate academic discipline, although he would not have approved of that characterization. Like many early computer designers, Bell was a tinkerer. A heart condition kept him close to the workshop of his father, an electrical and electronics repairman from second grade on. He was a computer designer, and his approach leaned heavily on his practical experience designing DEC’s PDP computers.
His famous textbook on computer architecture book had a long and storied life, beginning as collected readings and notes from the University of Michigan Press before Bell and Allen Newell collaborated on writing a textbook.

Bell and Olson mended fences, and Gordon returned to DEC in 1972 to create the famous VAX minicomputer. DEC sold approximately 400,000 VAXs during its 20-year production run from the 1970s to the 1990s. The VAX

put high performance technical computing on the desktops of engineers and scientists around the world. DEC continued to focus on high performance systems with the DEC Alpha, when Compaq purchased the company in 1998 and was in turn acquired by HP in 2001.

Bell’s Law

Everyone is familiar with is familiar with the law attributed to Gordon Moore (the founder of Fairchild Semiconductors) which states that the density of transistors on a chip doubles every 18 months, which halves the cost of semiconductors every 18 month. Moore’s Law is generally used to explain why the the capability of computers at a fixed cost doubles every 18 months The pace of chip manufcturing has slowed in recent years, so these days the doubling rate is closer to 24 months. It sounds technical, but in reality Moore’s Law is about money. Today, transistor density is still going up, but so is the price of semiconductors, which means that Moore’s Law is increasingly out of step with what drives costs in computing hardware.

Gordon Bell other} Gordon formulated Bell’s Law, which is not as famous at Moore’s but is more applicable to actual technology development because it is about systems, not transistors, and explains the emergence of media players, smartpjhones, tablets, cloud computing and more disruptive events A new lower priced class of computers emerges every decade based on disruptive advances in programming platforms, networks, and interfaces, which result in new use cases and the establishment of a new industry.

NSF

In 1986, he became Assistant Director of the National Science Foundation, where he founded the Computer and Information Science and Engineering Directorate. This was a time of upheaval and excitement in computer related research funding, and Bell played a major role in constructing today’s research infrastructure Tennessee Senator Al Gore was intrigued by the concept of an “information super highway”. Although we was roundly mocked in political circles, Gore was influenced by supercomputer development at Oak Ridge National Labs and began policy discussions in linking together labs, super computing facilities, and communication networks. In response, Congress set up cross-agency working groups to examine how this might be done. One of Bell’s roles in the new organziation at NSF was to ensure coordination among the various groups and agencies. By that time he had already formulated Bell’s Law and used his technical and persuasive skills—Which sometimes had the force of a battering ram to those on the other side of an argument to convince skeptical committee heads of the need ensure the health of the high performance computing industry.

The Gordon Bell Prize

One way to look at Bell’s Law is that improved performance and scalability are the result of intertwining of hardware and software innovation applied to increasingly difficult challenges in technical computing. That philosophy was enshrined in the Gordon Bell Prize, awarded annually by the ACM for achievement in technical parallel computing. The prize grew out of a letter from then IBM-numerical analyst Alan Karp to the editor of Communications of the ACM (CACM). wondered in print whether massively parallel MIMD processors was the best way to execute numerical algorithms and offered 100 dollar prize for convincing evidence otherwise. Karp said it was large enough to get attention but not so large to be a burden to pay if, as he suspected, someone would actually win it. Gordon liked the idea of a challenge that would track progress in parallel computing and endowed a $10,000 annual prize to be awarded for fundamental scientific breakthroughs with these goals:
* Reward practical use of parallel processors;
* Encourage improvements in hardware and software;
* Demonstrate the usefulness of parallel processors for real problems.

The first prize was awarded for work showing that Ahmdahl’s Law states that the overall speedup due to parallelism is limited by the proportion of code that cannot be parallized. In the 1967 AFIPS Spring Joint Computer Conference Amdahl stated and proved a result showing this in principle, there were proposals for alternative parallel architectures that could avoid the limitation. may not be insurmountable.
Over the years many contributions have been recognized by the Bell Prize.

This year’s Gordon Bell Prize was given to an International Team for Materials Simulations Which Achieve Quantum Accuracy at Scale. This work proposed a new framwork for ab initio real-time simulations. Quoting from the award citation: Despite the successes of ab initio approaches in a wide range of computer simulations, the team notes that efforts to employ quantum mechanical ab initio methods to predict materials’ properties has not been able to achieve quantum accuracy and scale on the powerful supercomputers needed to perform these simulations.

Microsoft, Silicon Valley, and Vanguard

The many published tributes to Bell’s life and career discuss his time in Silicon Valley, where he founded Microsoft’s Silicon Valley Laboratory. His book on capturing physical memory in digital form was one of his final works aimed at extending Bell’s Law to new applications such as nano-scale cardiac monitoring devices that could be woven into clothing.

Colleagues often remarked how easily Gordon slipped into his role a senior technologist during his years in Silicon Valley. Despite a reputation for being gruff, he was a personable and kind colleague. He helped Rich get situated when he moved from New Jersey to Palo Alto. Bell drove his Porsche 911 well into his 70’s. When he attended meetings at the San Jose Fairmont Hotel, the staff made sure it was parked in a visible location.

The gruff reputation was not entirely unearned, however. In the 1990’s Bell joined with other tech pioneers like Bell Labs’ Bob Lucky, UCLA’s Len Kleinrock, and MIT Media Lab’s Nicholas Negroponte to run a membership program called TTI Vanguard that had been spun out of Computer Science Corporation. Five times a year this wandering group of a hundred or so executives invited interesting high profile speakers to discuss candidly new results and innovations. Both of us attended regularly. The only rule of the Vanguard meetings was that the speaker must be given a ten-minute head start. At the ten-minute mark, Bell would inevitably be the first person to raise an interesting (and sometimes annoying) question or pose a problem that the speaker had overlooked. It was designed to be uncomfortable, and usually resulted in Gordon placing a bet on the other side of the speaker’s argument. The most memorable such encounter was Clayton Christensen’s presentation of The Innovator’s Dilemma. Christensen used the development of the PDP minicomputers as a case study for his theory that existing, successful tech companies are susceptible to innovation that takes them by surprise and eventually makes them obsolete. Bell did not give him the usual safety zone, He jumped to his feet, saying “I was there! It didn’t happen that way!” Christensen was a mild-mannered academic and completely unprepared for the assault. It was simultaneously the most uncomfortable and most entertraining such exchanges of all the Vanguard conferences.

More

Rich will add more in the future about Bell. We hope you enjoy these insights already.

It seems like we’ve been noticing 34 everywhere we look lately, whether it’s on billboards, in phone numbers, or even inside fortune cookies. Is it all just a coincidence? 34 is an angel number (a numeric message sent by your guardian angels) that symbolizes a new beginning.

Of course 34 is the key number that was used by a New York jury that found Donald Trump guilty on 34 felony charges of falsifying business records. Thus the number 34 is very important. Lets take a look at it:

It is the atomic number—34—for selenium. It is Se as a symbol and is a mineral found in the soil. It naturally appears in water and some foods. While people only need a very small amount, selenium plays a key role in their metabolism.

A Math View

As a math object 34 is:

* 34 (thirty-four) is the natural number following 33 and preceding 35.

* 34 is the magic constant of the 4×4 normal magic square.

* As a Roman numeral XXXIV and as a Binary number 0b100010.

* In numerology, 34 represents using creativity to achieve your goals.

* As the first Erdos—Woods \href{https://en.wikipedia.org/wiki/Erdos-Woods_number}{numbers} are
16, 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92, 94, 96, 100, 106, 112, 116 …

View

The so-called rules of the internet are not laws enforceable by any official authority. Rather, they are a series of in-jokes, guidelines, and references related to internet culture as it was in the early 2000s.

Thus rule 34, does for example, refer to the ubiquity of X-rated material online: “There is X-rated material of it. No exceptions.” Then, Rule 35 follows up: “The exception to rule 34 is the citation of rule 34.”

Open Problems

The number 34 is even famous in football. It includes the greats: Walter Payton, Earl Campbell, Thurman Thomas, Herschel Walker.

Perhaps what ever you feel about the recent events the number 34 will stay famous forever? It appears that many people are searching for the rule 34 after the verdict.