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 month in Knoxville, Tennessee. This is not the same as the Computational Complexity 2022 (CCC22) conference, which is being held in-person at the University of Pennsylvania this Wednesday, July 20, through Saturday, July 23. The Knoxville event is not about computer science, nor dynamical nor biological complexity. It is about the art of weaving complex patterns in textiles by hand.
Today we collect pointers to the papers at CCC22 after saying something separate about weaving and proofs.
Unlike CCC22, the Knoxville exhibition is also open online. Here is a detail from the Complex Weaver first prize winner, an example of three-dimensional weaving:
Like CCC22, the Knoxville event has a program committee. It consists of Julie Hedges, Robyn Spady, and Betty Vera. Also like CCC22, it has a steering committee. Besides Donde, the committee consists of Margaret Dugger, Diane Smith, Sarah Fortin, Susan Bowman, Eileen Hallman, Pat Brown, Katie Doan, Geri Forkner, Cathy McCarthy, Ruth MacGregor, and Cally Booker. The gender imbalance is more extreme than for CCC22 or what we noted last fall for POPL22 (also see end of this). Oh well.
Weaving Into Theory
Karen Donde also writes a blog, Speaking of Weaving. The blog has numerous technical how-to articles. In some places they verge on mathematical theory.
There are more express connections between mathematics and weaving. The mathematics teacher Patrick Honner has a page of posts on weaving. He was featured in an article “Weaving your way through mathematics” by the mathematics educator Maria Droujkova. See also a video on weaving and the mathematics of Spirograph patterns.
On the computing theory side, connections to cellular automata are shown in a 2017 paper by Joshua Holden. There is also a recent paper from CMU’s Human-Computer Interaction Institute on “Enabling Personal Computational Handweaving with a Low-Cost Jacquard Loom.”
Weaving Into Proofs
Our association to weaving was really motivated, however, by an article last Wednesday by Steven Strogatz, a Cornell mathematician and extraordinary popularizer whom I (Ken) have known since we were undergraduates together at Princeton. The article interviews the Harvard mathematician Melanie Matchett Wood and is titled, “How Do Mathematicians Know Their Proofs Are Correct?”
We have written about proofs and the social issue of verification several times recently. But this article goes into a more particular topic that we tried to get at in a series of posts in 2014. This is about whether probabilistic modeling—not the Probabilistic Method which is airtight—can give confidence in conjectures that is tantamount to proof.
Strogatz’s interview leads off with a reference to a 2019 article for Quanta titled, “Where Proof, Evidence, and Imagination Intersect.” That article is by the same Patrick Honner whom we just mentioned for weaving, and gives caveats of how bias and unrecognized implicit constraints can creep into models, so as to invalidate them.
Wood begins with basic “coinflip” random models of primes—such as mentioned in the above-listed posts—and fixes on a bias-revealing model that we also covered here. She then describes how they incrementally build rules for adjusting coin weights to compensate for biases introduced by small-number cases:
“So the model is something that starts with this coin-flipping model, but then it’s modified by all these other rules, and all the other things that we know about the primes. And once you put all of those things that we do know into the model, you then ask [it] well, do you see, infinitely often, coins coming up prime just 2 apart? And the model tells you, oh, yes, we do see that. In fact, we see it at this very particular rate we can give you a formula for. And then … you see that the model gives you a very accurate prediction for the number of pairs of twin primes you’ll find as you go along. And so then you think, you know, maybe this model knows what it’s talking about.”
In response to Strogatz noting that the accuracy must be judged by long computer runs, Wood is quick to emphasize that the rules given to the model are determined manually:
“But for building this model and coming up with the formula that the model gives. You know, that’s done by hand, essentially, by mathematicians thinking about the model and figuring out with it. … [A]t some point, the computer stops. You know, there’s only so much computing power. But that formula that you would get, that the model would give you, that you could prove is true, again, about this model coin-flipping situation, that formula will keep going. You can put bigger and bigger numbers into that formula, much bigger than your computer could ever, ever compute with.”
Proof of the Loom?
Wood goes on to describe universality in probability theory as signifying “that there are certain kinds of machines that if you put in a lot of random inputs, you can predict the output.” She gives as a bellwether example how the Central Limit Theorem creates such a universal machine for the bell curve. Regardless of an unknown distribution D, if you take means of samples from D, then the bell curve gives progressively—and provably—more accurate predictions of your outputs. Strogatz catches the warp and asks whether “somehow we’re getting the idea of universality to show up in number theory? Or am I dreaming?” Her peroration is:
“[W]hat my collaborators and I work on is trying to make that kind of dream a reality so that, that some of these puzzling questions about numbers that we don’t know the answer to, maybe we could understand that there are patterns that come out, like a bell curve, like a normal distribution, that we can prove came out of the machine even if we don’t know what mysteries were put in.”
So she is building a machine that takes rules as input—like Jacquard cards for a loom—and produces patterns that are analyzable. We use the computational success of the machine to judge how well universality has taken hold—as theoretically it must—and generate proofs from formulas based on the a-priori predicted outputs using the rules input thus far.
This is like building a loom for weaving proofs—where, however, there is still the question of confidence in how well the patterns obtained match reality. Such doubt notwithstanding, the process may also augment non-linear ways of evaluating claimed proofs of the kind we discussed here and recently debated here.
The Papers
The proofs in the accepted papers were, to be sure, evaluated by the standard expert social process. Here they are, lifted from the conference’s own program page. Clicking on the time of the talk gives a pointer to the paper.
Wednesday, July 20
9:00 “Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes.”
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan
9:30 “New Near-Linear Time Decodable Codes Closer to the GV Bound.”
Guy Blanc and Dean Doron
10:00 “The plane test is a local tester for Multiplicity Codes.”
Dan Karliner, Roie Salama and Amnon Ta-Shma
13:30 “Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle” (co-winner Best student paper).
Oliver Korten
14:00 “Nisan-Wigderson generators in Proof Complexity: New lower bounds.”
Erfan Khaniki
14:30 “Pseudorandom Generators, Resolution and Heavy Width.”
Dmitry Sokolov
15:30 “Hitting Sets for Regular Branching Programs.”
Andrej Bogdanov, William Hoza, Gautam Prakriya and Edward Pyne
16:00 “Improved Pseudorandom Generators for 
Xin Lyu
16:40 “Random restrictions and PRGs for PTFs in Gaussian Space.”
Zander Kelley and Raghu Meka
17:00 “Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs.”
Louis Golowich and Salil Vadhan
Thursday, July 21
9:00 “Quantum search-to-decision reductions and the state synthesis problem.”
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao and Henry Yuen
9:30 “Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms.”
Nikhil Bansal, Makrand Sinha and Ronald de Wolf
10:00 “The Acrobatics of BQP” (winner – Best paper award).
Scott Aaronson, Devon Ingram and William Kretschmer
13:30 “On One-way Functions from NP-Complete Problems.”
Yanyi Liu and Rafael Pass
14:00 “Finding Errorless Pessiland in Error-Prone Heuristica.”
Shuichi Hirahara and Mikito Nanashima
14:30 “Characterizing Derandomization Through Fine-Grained Hardness of Levin-Kolmogorov Complexity.”
Yanyi Liu and Rafael Pass
15:30 “Almost Polynomial Factor Inapproximability for Parameterized k-Clique.”
Karthik C. S. and Subhash Khot
16:00 “Certifying solution geometry in random CSPs: counts, clusters and balance.”
Jun-Ting Hsieh, Sidhanth Mohanty and Jeff Xu
16:40 “High-Dimensional Expanders from Chevalley Groups.”
Ryan O’Donnell and Kevin Pratt
17:10 “The composition complexity of majority.”
Victor Lecomte, Prasanna Ramakrishnan and Li-Yang Tan
Friday, July 22
9:00 “The Approximate Degree of Bipartite Perfect Matching.”
Gal Beniamini
9:30 “Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation.”
Amol Aggarwal and Josh Alman
10:00 “
Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff
13:30 “On Randomized Reductions to the Random Strings.”
Michael Saks and Rahul Santhanam
14:00 “Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.”
Lijie Chen, Jiatu Li and Tianqi Yang
14:30 “A better-than-3log(n) depth lower bound for De Morgan formulas with restrictions on top gates.”
Ivan Mihajlin and Anastasia Sofronova
15:30 “Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.”
Halley Goldberg, Valentine Kabanets, Zhenjian Lu and Igor C. Oliveira
16:00 “Symmetry of Information from Meta-Complexity.”
Shuichi Hirahara
16:30 “On the Satisfaction Probability of k-CNF Formulas.”
Till Tantau
Saturday, July 23
9:00 “On Efficient Noncommutative Polynomial Factorization via Higman Linearization.”
Vikraman Arvind and Pushkar Joglekar
9:30 “Improved Low-Depth Set-Multilinear Circuit Lower Bounds.”
Deepanshu Kush and Shubhangi Saraf
10:15 “On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials.”
Nutan Limaye, Srikanth Srinivasan and Sebastien Tavenas
10:45 “Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors.”
Harm Derksen, Visu Makam and Jeroen Zuiddam
11:00 “Trading Time and Space in Catalytic Branching Programs.”
Ian Mertz and James Cook
12:30 “Linear Branching Programs and Directional Affine Extractors.”
Svyatoslav Gryaznov, Pavel Pudlak and Navid Talebanfard
14:00 “Further collapses in TFNP.”
Mika Goos, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere and Ran Tao
14:30 “Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes.”
Sarah Bordage, Mathieu Lhotel, Jade Nardi and Hugues Randriam
15:00 “Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs.”
Gal Arnon, Alessandro Chiesa and Eylon Yogev
We congratulate all the authors of the accepted papers.
Open Problems
Can we really build mathematical looms for helping us generate proofs at high level?
Trackbacks