select refs and big tribute to empirical CS/ math

1 Reply

LittleComputer💡 ❗ ⭐ 😎 ❤ 😀 hi all, this post spent a long time in the works/ “drawing board” building up & now finally decided to “clean house” after it all finally seemed to reach “critical mass” at least in my bookmark pile. it is difficult to time it. empirical CS/ math has been a big topic in the past on this blog.[a15][a16] this can be a controversial area for multiple reasons/ “standard objections”. there are occasional large breakthrus in this area. however, they are not widely known/ heralded and sometimes even quickly forgotten. one might imagine the momentum steadily building in this area but it seems to be very uneven in progress/ attention. over the last few years here are a few key experimental breakthrus reported but not widely appreciated:

  • decrease of the gap in the Zhang twin primes proof. some of this work was done with experimental/ computer searches that found smaller gaps which were then verified/ proven mathematically. its as if numerical evidence gives theoreticians confidence to find/ nail down abstract proofs (instead of hunting for something that might not exist).
  • the big-award-winning Kadison Singer proof by Spielman et al.; was aware of this proof but was not even aware myself of the empirical component until the recent writeup by Klarreich for the Simons Quanta magazine.[b] after this account, one wonders if the proof would even have been found/ possible without computer experiments! she writes: (this reminds me of binet’s formula for fibonacci numbers!)

Spielman, Marcus and Srivastava suspected that the answer was yes, and their intuition did not just stem from their previous work on network sparsification. They also ran millions of simulations without finding any counterexamples. “A lot of our stuff was led by experimentation,” Marcus said. “Twenty years ago, the three of us sitting in the same room would not have solved this problem.”

The simulations convinced them that they were on the right track, even as the problem raised one stumbling block after another. […]

A network’s electrical properties are governed by a special equation called the network’s “characteristic polynomial.” As the trio performed computer experiments on these polynomials, they found that the equations seemed to have hidden structure: Their solutions were always real numbers (as opposed to complex numbers), and, surprisingly, adding these polynomials together always seemed to result in a new polynomial with that same property. “These polynomials were doing more than we gave them credit for,” Marcus said. “We used them as a way of transferring knowledge, but really the polynomials seemed to be containing knowledge themselves.”

  • the Erdos Discrepancy Problem results by Konev/ Lisitsa. this got a lot of attention and plausibly played a role in the recent proof by Tao. again, the pattern of solid numerical results found by experimentalists give mathematician(s) confidence to tackle previously un-conjectured results.
  • a new pentagonal tiling has been found and caused major surprise/ ripples in the area.[r]

“We discovered the tile using using a computer to exhaustively search through a large but finite set of possibilities,” said Casey. “We were of course very excited and a bit surprised to find the new type of pentagon.

  • Fermi-Pasta-Ulam nonlinear physics/ applied math problem recently subject to major advance.[q4]

“Thanks to this lateral approach, we partially answered the 60-year-old FPU problem. We were able to predict the long thermalization timescale knowing the initial conditions of the system. We also corroborated our theoretical result with extensive numerical simulations.

😮 the excellent/ striking Kadison-Singer writeup by Klarreich and the nearly-eyepopping excerpt above was one trigger for this post. how many people were aware of their central/ pivotal computer experiments? are they even referred to in their writeups anywhere? it is likely buried somewhere if mentioned at all, and that is something of a shame. but, this is not surprising/ typical and par for the course in this area.

the new detailed behind-the-scenes account also makes one wonder if mathematicians or “CSists” were a little more flexible and experimental whether major new insights would be possible. after many years of studying this, think most lack of progress in hard problems is mainly due to their inherent difficulty, but maybe at least some small part is psychological, sociological, cultural, and conventional.

mathematicians and computer scientists routinely express ignorance and at times even some disdain for coding/ experimentation. the title of that CS stackexchange question is “how can I teach CS without computers?” wow, a near zen question if I ever heard one! sounds to me sort of like, “what is the sound of one hand clapping?” or, “how do I teach bicycle riding without using bicycles”? this all seems near/ reminiscent of the semifamous/ notorious (to me) quote attributed to Dijkstra, “CS is no more about computers than astronomy is about telescopes.” my contrarian position to that would be simply that “advanced astronomy is impossible without telescopes” and “the better the telescopes, the better the astronomy.”

astronomy did advance during and prior to the dark ages, but it was (a lot of tautologies around here!) dark and pre-dark age astronomy, also pre-enlightenment “science”! however, all that said, do very much like the yin-yang theoretical/ applied dichotomy/ juxtaposition evident in both fields though, and the analogy/ parallel of exploration of terra incognita in synergy between mind and matter, knowledge and tools, and theory/ application.

so have been waiting for awhile for a big empirical breakthru in CS/ math that makes the front pages of science journals. but this has not materialized. on the other hand my links runneth over. so am going to get out ahead of the pack on this one and write all this up, and also in some anticipation of major/ imminent advances in the area, but (alas) nothing in particular at the moment.

my list of favorite/ notable/ leading (“hall of fame”) CS empirical researchers in case anyone questions that angle:

  • founder of the field Knuth did a lot of empirical work in the Art of Computer Programming. some of this has been lost in memory. wish someone (or he himself!) would do a survey of his empirical work.
  • Doron Zeilberger is famous for his empirical work.[h6]
  • Sedgewick has spoken/ written eloquently on the role of empirical aspects of algorithmic research.[a4][a5]
  • Lipton has also blogged on this “flip side” somewhat under the topic of “galactic algorithms” ie unwieldy algorithms that are not implemented in practice, whether program size matters, etc.[n]
  • CS “forefather” Turing himself had a very applied side, eg in inventing/ working on one of the worlds 1st computers during WWII. this story was not very well known previously but very deservedly got the 7-oscar-nominated treatment in Imitation Game.
  • “imho” one of the greatest ever empirical theoreticians (yes, its an oxymoron) is the living Wolfram with his ambitious, meticulous, copious, monolithic, near-encyclopedic inquiry into cellular automata. alas, hes a highly controversial and polarizing figure at times, something like the “rodney dangerfield” of researchers with many other academics and scientists criticizing his style etc.

some neat hilights, Mitzenmacher has recently emerged as a big proponent/ advocate/ defender with a big essay in the CACM.[a6][m1] the Simons institute and Klarreich are hot on the tail of empirical approaches in crosscutting areas of CS/ math/ applications.[a9][b11][h2][h6] re CACM profile/ advocation see also [h3].

the concept of “galactic algorithms” seems a bit slippery. it originally seemed to be coined to refer to very complex algorithms that have good theoretical performance. but then there is the concept of implementation difficulty that inevitably creeps in. so “galactic algorithms” term (only relatively recently coined by Lipton) seems to me to be subject to the “elephant and the blind men” aka “rashomon” phenomenon.

it is a bit of a philosophical distinction in some ways whether a theoretical algorithm is implemented, and in other ways its a very practical, pragmatic question. this is the CS version of “long proofs” eg from mathematics like the Classification of Finite Simple Groups which spans thousands of research pages and which (mostly/ apparently) has never actually been “implemented” in code.[m4]

so ideas about program verification and proof correctness/ verification also enter here.[h] it is somewhat taboo to talk about erroneous proofs/ papers in either CS or math, but from an implementers pov, this is a key aspect of human! science.

there is a lot of innovation in empirical approaches, eg notably in sorting networks charging ahead,[e] and eg in an area dear to my heart, SAT, namely ASP and SMT programming.[i][j] (oh, and they are related; the new sorting network results/ proofs are largely based on SAT solvers.)

have very long thought/ proposed (~2 decades!) that studying SAT instances empirically could lead to major insight into problem hardness esp with factoring, but this work is mostly not even undergone by the theoretical/ applied community because its a mostly crosscutting idea that tends to “fall through the cracks”.[g] however [c14] is a 100p(!) masters thesis by Herwig that does innovative/ creative/ groundbreaking work in the area, which seems not to have been cited or advanced on much.

there is a US govt recognition/ funding initiative called NSF “AitF/8F”, “algorithms in the Field,” so now with real dollars involved you know its real.[k]

memcomputing has some wild claims and most theoretical researchers are not taking it too seriously (Aaronson has lambasted it), but, personally avoiding knee-jerk reaction, it looks to have innovative elements and promise to me and think there is some irrational pushback/ overreaction typical of the “anti experimental bias” that pervades “classic” math/ CS.[l] my thinking is that maybe there are tricky/ “slow” scalability or noise issues on the efficiency claims that are difficult to untangle/ observe at “low datapoints”. that may sound like handwaving but its nearly exactly the same case for quantum computing—exactly the kind of thing that interdisciplinary, theorist/ applied-crosscutting-mix experts can help with.

overall this whole picture combined represents a paradigm shift in math and computer science, but few have noticed or documented it overall.[a][h] it appears to me despite decades of use/ application in the area, the use of computers in science research is probably in its infancy and its penetration/ increase is part of a very long wave spanning many decades, easily more than a ½ century.

it may seem counterintuitive but in my thinking, but maybe not within the reductionistic/ overspecialized/ compartmentalized tendency of modern science, both Big Data and Deep Learning are unequivocally aspects of empirical computer science. this gives the overall field some major/ intense rocket fuel/ full engine/ throttle/ thrust ahead! deep learning is being used mainly for object and speech recognition advances, but think it may lead to mathematics and CS research advances in the not-so-distant future. this is not completely outlandish and has been long envisioned by other visionary authors/ authorities, eg most notably Gowers (see earlier blog on that).[a16]

addendum: [p] are refs turned up with google. several (about ½ dozen) classes/ syllabuses around the internet. speaking of “long forgotten,” [p1] is a Turing Award lecture by Newell and Simon from 1975, “Computer Science as Empirical Science”. their award was for “basic contributions to artificial intelligence, the psychology of human cognition, and list processing” but they took the opportunity to emphasize the empirical aspects of computer science.

addendum2: [q][r] connections to mathematics such as the recent periodic pentagon tiling proof found empirically, theorem proving and verification, etc.

 

a. experimental2
b. spielman/kadison/singer
c. papers
d. books
e. sorting networks
f. stackexchange Q/A
g. fact2sat
h. empirical math
i. asp
j. smt
k. NSF Algorithms in the Field “8F”
l. memcomputing
m. powerful/ complex/ galactic/ practical/ erroneous
n. lipton
o. (SE Q/A) correctness/ implementation
p. experimental3
q. computer math
r. pentagon tiling

1 thought on “select refs and big tribute to empirical CS/ math”

  1. Pingback: norbert blum P vs NP attack goes CYBER-SCIENCE-VIRAL! | Turing Machine

Leave a comment