Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Enjoying Idaho while ignoring Illinois Today is the first day of my life that I am unemployed. And not by choice. As I mentioned on LinkedIn last week, me and about 160 of my colleagues, staff and faculty, untenured and tenured, lost our positions at Illinois Tech after they declared "financial exigency" which allows them to eliminate tenured positions. I'll use this post to tell my story, but…
(Some of this came from a Reddit post I read, and some of the comments on it.) Here are theorems with names that I think are funny or unusual. The names are also pointers to the Wikipedia entry on them or some other source. The Chicken McNugget Theorem The Ham Sandwich Theorem The Hairy Ball Theorem Freshman Dream The law of the unconscious statistician The Homicidal Chauffeur Problem The…
I was watching a Jeopardy from 2004 (The Game Show Channel is rerunning Ken Jennings streak) and the following question raises a good question. The contestants where Ken, Jerry, Jennifer. In Double Jeopardy there was a category Biblical Name The Same. The clue was three last names (e.g., Driver, Sandler, West ) and the correct response is a biblical name that is the first name of people with that…
Let's say there is a statement in math T that you wonder whether it's true or false. You may even make a conjecture of which way it goes. Do you have a rooting interest? I may think T is true, but if someone proves T or proves NOT(T) my main concerns are (1) can I understand the proof ? (2) is the proof interesting? Paul Erdos posed the sum-product conjecture which was recently proven false (by…
Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week where I would take some interesting complexity class, write down on a white board everything we knew about it with some open problems and students and faculty would muse over it. When I started the blog in 2002, I took the concept online . My first Complexity Class of the Week…
Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf. The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it? We will assume that the reader is an…
Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birthday. Let me talk about his most famous work, the Chernoff Bounds themselves. If you have a coin that will be heads with probability \(p\), and you flip it \(n\) times, the expected number of heads is \(pn\). Informally Chernoff bounds says that for large \(n\)…
The excellent graphic novel Prime Suspects: The Anatomy of Integers and Permutations by Andrew Granville and Jennifer Granville, illustrated by Robert J Lewis, (I wrote a review of this graphic novel, for SIGACT News, here .) has an appendix, which is not in graphic-novel form, where they describe some of the math talked about in the graphic novel. Here is a quote that intrigued me for two reasons…
Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself. Jim Larus, editor-in-chief of the CACM, writes Wither ACM? Publish and Perish? ACM no longer has broad appeal as a professional organization, does not advance many members’ careers, and may not be a valuable affiliation in a more diverse…
I recently read Alan Alda's first memoir Never have your dog stuffed which was pretty good. Hence I began looking for more information about him on the web. I came across a YouTube video At 89, Alan Alda reveals the seven actors he HATED the most . Gee, in the book he didn't hate anyone. So I was curious what this was about. This could be interesting. It was not . The title was extremely…
Harry Lewis pointed Bill and me to Gottfried Leibniz's 1677 treatise The True Method (translated from the original French ). I highly recommend taking the time to read this three page document where he talks about formalizing all human knowledge. The second paragraph has some of the intuition for P v NP three centuries before Cook, Levin and Gödel . But knowledge depends on proof, and discovering…
Peter Brass is a prior NSF theory director. He has written an intelligent guest post on the new NSF guidelines that we present here. You have received many mails regarding the proposed OMB Uniform Guidance for federal grant making. It is a very long document. So far the OMB has received more than 32,000 comments, which nominally all will be read and taken into account, but actually most are…
When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on…
(All references in this blog post can be found in the main article the post is about which is here .) Recall that \(R(s,k) \) is the least \(n\) so that, for all 2-colorings of the edges of \(K_n\), there is either a RED \(s\)-clique or a BLUE \(k\)-clique. \(R(k,k)\) has been well studied and is often called \(R(k)\). However, today we are concerned with \(R(s,k)\) \(s\) is fixed and \(k\) goes…
Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road , a network of trading routes across Asia active from the second century BCE until the mid-15th century. I knew of the Silk Road but was surprised by how much it used and fostered various technologies. It started with a technology that allowed for traveling long distances with limited access to water,…
A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is My Very Educated Mother Just Said Uh, No Pluto You probably know what it's for. If not you can type it into Google and you will find: Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune and of course NOT Pluto anymore. Consider Kids Prefer Cheese Over Fried Green…
There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as the more intuitive notion that everything efficiently verifiable is efficiently computable and the implications that has on our ability to compute. I've written considerably about how artificial intelligence has affected the latter. In particular, how AI and…
(In 2008 I wrote a survey of some of the known sum-product theorems, see here . Avi Wigderson has a great slide-set on sum-product theorems and their applications---the slides are on Avi's webpage of talks he has given (all the talks are excellent) which is here . I had a prior post on sum-product theorems here ) If \(A\) is a set then let \(A+A = \{ x+y \ \colon\ x,y\in A \} \), \(A\cdot A = \{…
Yesterday, National Academy of Sciences President Marcia McNutt delivered her last annual State of the Sciences Address . Overall the talk basically calls us to adapt to the new reality that industrial and foundation support for research has taken a far larger role in academic research. I fear we may be losing the broad academic independence and exploration that has made our universities the envy…
Odd Scenarios about Research Claims I blogged about OpenAI's achievement of having AI solve a math problem here . My post had a few comments about authorship of such results. Lance had a post about co-authorship and AI here There are times when an author on a paper prefers to not be listed as a co-author. There are times when an author wants to give credit in odd places. We give some scenarios. 1)…
The technical paper for the Erdős Unit Distance Problem lists only "OpenAI" as an author. When Bill posted on Sunday about the Erdős distance problems, he mentioned the names of OpenAI researchers who prompted and checked the proof. Sebastien Bubeck of OpenAI reached out directly and later as a comment saying this was really an OpenAI-wide achievement, and we shouldn't just single out people at…
In a 1946 paper in the American Mathematical Monthly, Paul Erdős posed the Erdős Distinct Distance Problem and the Erdős Unit Distance Problem. -------------------------------------------------------------------- THE ERDŐS DISTINCT DISTANCE PROBLEM A nice high school math competition problem, if it were not fairly well known, is: Show that for all sets of \(n\) points in the plane, there are at…
Let \(f\) be a function mapping binary strings of length \(m\) to strings of length \(n\) with \(n>m\). Since there are more strings of length \(n\) than \(m\), \(f\) is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short Let's do an example. Consider \(f\) that outputs an undirected graph on \(n\) nodes and takes as input: \(n\) A…
1) Congratulations to Scott Aaronson for winning the first Trevisan Award. The Trevisan Award is in memory of Luca Trevisan and recognizes expository work in Theoretical Computer Science. It is given out by the ACM. The ACM announcement of Scott's award is here . Scott blogged about winning it here . 2) When preparing this blog post, I googled Trevisan Award. The first hit I got was this . That…
For those very long-time readers this blog extensively covered prediction markets from 2006 to 2008. In a prediction market, you have a future event, such as the winner of an election, and a market that pays off one dollar if that event happens and nothing if it doesn't. The price of this market corresponds to a predicted probability that the event will happen. I worked with David Pennock and…