Tuesday, July 16, 2019
Guest post by Samir Khuller on attending The TCS Women 2019 meeting
(I will post the solution to the problem in the last blog later in the week---probably Thursday. Meanwhile, enjoy these thoughts from Samir Khuller on the TCS Women 2019 meeting.)
Guest Post by Samir Khuller:
Am I even allowed here?” was the first thought that crossed my mind when I entered the room. It was packed with women (over 95%), however a few minutes later, several men had trickled in. I was at the TCS Women spotlight workshop on the day before STOC. Kudos to Barna Saha, Sofya Raskhodnikova, and Virginia Vassilevska Williams for putting this grand (and long needed) event together, which serves as a role model and showcases some of the recent work by rising stars. In addition to the Sun afternoon workshop, the event was followed by both an all women panel and a poster session (which I sadly did not attend).
The rising stars talks were given by Naama Ben-David (CMU), Andrea Lincoln (MIT), Debarati Das (Charles University) and Oxana Poburinnaya (Boston U). After a short break the inspirational talk was by Ronitt Rubinfeld from MIT. Ronitt’s talk was on the topic of Program Checking, but she made it inspirational by putting us in her shoes as a young graduate student, three decades back, trying to make a dent in research by working on something that her advisor Manuel Blum, and his senior graduate student Sampath Kannan had been working on, and I must say she made a pretty big dent in the process! She also related those ideas to other pieces of work done since in a really elegant manner and how these pieces of work lead to work on property testing.
I am delighted to say that NSF supported the workshop along with companies such as Amazon, Akamai, Google and Microsoft. SIGACT plans to be a major sponsor next year.
The Full program for the workshop is at the following URLhere.
Sunday, July 14, 2019
Two infinite hat problem and a question about what is ``well known''
This is a joint post with David Marcus. You will see how he is involved in my next post.
Two infinite hat problems based on one scenario. I am also curious if they are well known.
1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own.
2) The adversary is going to put hats on all the people. They will guess their own hat color at the same time.
3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy.
4) The people want to minimize how many they get wrong.
5) The adversary puts on hats to maximize how many they get wrong.
I ask two questions and one meta-question:
Q1: Is there a solution where they get all but a finite number of the guesses right? (I have blogged about a variant of this one a while back.)
Q2: Is there a solution where they get all but at most (say) 18 wrong. (My students would say the answer has to be YES or he wouldn't ask it. They don't realize that I work on upper AND lower bounds!)
Q3: How well known is problem Q1 and the solution? Q2 and the solution? I've seen Q1 and its solution around (not sure where), but the only source on Q2 that I know of is CAN'T TELL YOU IN THIS POST, WILL IN THE NEXT POST. So, please leave a comment telling me if you have seen Q1 or Q2 and solutions. And if so then where.
Feel free to leave any comments you want; however, I warn readers who want to solve it themselves to not look at the comments, or at my next post.
Thursday, July 11, 2019
Degree and Sensitivity
Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992 result of Gotsman and Linial. Let's talk about that result.
Consider the set S={-1,1}n. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x1,…,xn) and y = (y1,…,yn) in S if there is exactly one i such that xi ≠ yi. Every vertex has degree n.
We say a vertex x is odd if x has an odd number of -1 coordinates, even otherwise. Every edge joins an odd and even vertex.
Let f be a function mapping S to {-1,1}. The sensitivity of f on x is the number of i such that f(x1,…,xi,…,xn) ≠ f(x1,…,-xi,…,xn). The sensitivity of f is the maximum over all x in S of the sensitivity of f on x.
Let g be the same function as f except that we flip the value on all odd vertices. Notice now that the sensitivity of f on x is the number of i such that g(x1,…,xi,…,xn) = g(x1,…,-xi,…,xn).
Let G be the induced subgraph of vertices of x such that g(x)=-1 and H be induced subgraph on the set of x such that g(x)=1. The sensitivity of f is the maximum number of neighbors of any vertex in G or H.
Consider f as a multilinear polynomial over the reals. The sensitivity conjecture states there is some α>0 such that if f has degree n then f has sensitivity at least nα.
Note g(x1,…,xn)=f(x1,…,xn)x1⋯xn. If f has a degree n term, the variables in that term cancel out on S (since xi2=1) and the constant of the degree n term of f becomes the constant term of g. The constant term is just the expected value, so f has full degree iff g is unbalanced.
GL Assumption: Suppose you have a partition of the hypercube into sets A and B with |A| ≠ |B|, and let G and H be the induced subgraphs of A and B. Then there is some constant α>0 such that there is a node of A or B with at least nα neighbors.
The above argument, due to Gotsman and Linial, shows that the GL assumption is equivalent to the sensitivity conjecture.
Huang proved that given any subset A of the vertices of a hypercube with |A|>2n/2 the induced subgraph has a node of degree at least n1/2. Since either A or B in the GL assumption has size greater than 2n/2, Huang's result gives the sensitivity conjecture.
Consider the set S={-1,1}n. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x1,…,xn) and y = (y1,…,yn) in S if there is exactly one i such that xi ≠ yi. Every vertex has degree n.
We say a vertex x is odd if x has an odd number of -1 coordinates, even otherwise. Every edge joins an odd and even vertex.
Let f be a function mapping S to {-1,1}. The sensitivity of f on x is the number of i such that f(x1,…,xi,…,xn) ≠ f(x1,…,-xi,…,xn). The sensitivity of f is the maximum over all x in S of the sensitivity of f on x.
Let g be the same function as f except that we flip the value on all odd vertices. Notice now that the sensitivity of f on x is the number of i such that g(x1,…,xi,…,xn) = g(x1,…,-xi,…,xn).
Let G be the induced subgraph of vertices of x such that g(x)=-1 and H be induced subgraph on the set of x such that g(x)=1. The sensitivity of f is the maximum number of neighbors of any vertex in G or H.
Consider f as a multilinear polynomial over the reals. The sensitivity conjecture states there is some α>0 such that if f has degree n then f has sensitivity at least nα.
Note g(x1,…,xn)=f(x1,…,xn)x1⋯xn. If f has a degree n term, the variables in that term cancel out on S (since xi2=1) and the constant of the degree n term of f becomes the constant term of g. The constant term is just the expected value, so f has full degree iff g is unbalanced.
GL Assumption: Suppose you have a partition of the hypercube into sets A and B with |A| ≠ |B|, and let G and H be the induced subgraphs of A and B. Then there is some constant α>0 such that there is a node of A or B with at least nα neighbors.
The above argument, due to Gotsman and Linial, shows that the GL assumption is equivalent to the sensitivity conjecture.
Huang proved that given any subset A of the vertices of a hypercube with |A|>2n/2 the induced subgraph has a node of degree at least n1/2. Since either A or B in the GL assumption has size greater than 2n/2, Huang's result gives the sensitivity conjecture.
Sunday, July 07, 2019
Fortran is underated!
(Joint Post with David Marcus who was a classmate of mine at SUNY Stony Brook [now called Stony Brook University]. I was class of 1980, he was class of 1979. We were both math majors.)
David has been reading Problems with a POINT (I'm glad someone is reading it) and emailed me a comment on the following passage which was essentially this post. I paraphrase what I wrote:
PASSAGE IN BOOK:
I dusted off my book shelves and found a book on Fortran. On the back it said:
FORTRAN is one of the oldest high-level languages and remains the premier language for writing code for science and engineering applications. (NOTE- The back of the book uses Fortran but the spell checker I am using insists on FORTRAN. As a fan of capital letters, I don't mind going along.)
When was the book written?
The answer was surprising in that it was 2012 (the Chapter title was Trick Question or Stupid Question. This was a Trick Question.) I would have thought that FORTRAN was no longer the premier language by then. I also need to dust my bookshelves more often.
END OF PASSAGE IN BOOK
David Marcus emailed me the following:
DAVID'S EMAIL
Page 201. Fortran. One clue is that it said "Fortran" rather than"FORTRAN". Fortran 90 changed the name from all upper case. Whether it is the "premier language" depends on what you mean by "premier". It is probably the best language for scientific computing. I used it pretty much exclusively (by choice) in my previous job that I left in 2006. The handling of arrays is better than any other language I've used. Maybe there are some better languages that I'm not familiar with, but the huge number of high-quality scientific libraries available for Fortran makes it hard to beat. On the other hand, I never wrote a GUI app with it (Delphi is best for that).
END OF DAVID'S EMAIL
In later emails we agreed that Fortran is not used that much (there are lists of most-used languages and neither Fortran nor FORTRAN is ever in the top 10). But what intrigued me was the following contrast:
1) David says that its the BEST language for Scientific Computing. I will assume he is right.
2) I doubt much NEW code is being written in it. I will assume I am right.
So---what's up with that? Some options
OPTION 1) People SHOULD use Fortran but DON'T. If so, why is that? Fortran is not taught in schools. People are used to what they already know. Perhaps people who do pick up new things easily and want to use new things would rather use NEW things rather than NEW-TO-THEM-BUT-NOT-TO-THEIR-GRANDMOTHER things. Could be a coolness factor. Do the advantages of Fortran outweight the disadvantages? Is what they are using good enough?
OPTION 2) The amount of Scientific computing software being written is small since we already have these great Fortran packages. So it may be a victim of its own success.
CAVEAT: When I emailed David a first draft of the post he pointed out the following which has to do with the lists of most-used programming languages:
DAVIDS EMAIL:
The problem with the lists you were looking at is that most people in the world are not scientists, so most software being written is not for scientists. Scientists and technical people are writing lots of new code. If you look at a list of scientific languages, you will see Fortran, e.g., here and here.
There are several Fortran compilers available. One of the best was bought by Intel some time back and they still sell it. I doubt they would do that if no one was using it. Actually, I think Intel had a compiler, but bought the Compaq compiler (which used to be the Digital Equipment compiler) and merged the Compaq team with their team. Something like that. I was using the Compaq compiler around that time.
END OF DAVID's EMAIL
One quote from the second pointer I find intriguing. (Second use of the word intriguing. It was my word-of-the-day on my word-calendar).
... facilities for inter-operation with C were added to Fortran 2003 and enhanced by ISO/ICE technical specification 29113, which will be incorporated into Fortran 2018.
I (Bill) don't know what some of that means; however, it does mean that Fortran is still active.
One fear: with its not being taught that much, will knowledge of it die out. We be like Star Trek aliens:
The old ones built these machines, but then died and we can't fix them!
David has been reading Problems with a POINT (I'm glad someone is reading it) and emailed me a comment on the following passage which was essentially this post. I paraphrase what I wrote:
PASSAGE IN BOOK:
I dusted off my book shelves and found a book on Fortran. On the back it said:
FORTRAN is one of the oldest high-level languages and remains the premier language for writing code for science and engineering applications. (NOTE- The back of the book uses Fortran but the spell checker I am using insists on FORTRAN. As a fan of capital letters, I don't mind going along.)
When was the book written?
The answer was surprising in that it was 2012 (the Chapter title was Trick Question or Stupid Question. This was a Trick Question.) I would have thought that FORTRAN was no longer the premier language by then. I also need to dust my bookshelves more often.
END OF PASSAGE IN BOOK
David Marcus emailed me the following:
DAVID'S EMAIL
Page 201. Fortran. One clue is that it said "Fortran" rather than"FORTRAN". Fortran 90 changed the name from all upper case. Whether it is the "premier language" depends on what you mean by "premier". It is probably the best language for scientific computing. I used it pretty much exclusively (by choice) in my previous job that I left in 2006. The handling of arrays is better than any other language I've used. Maybe there are some better languages that I'm not familiar with, but the huge number of high-quality scientific libraries available for Fortran makes it hard to beat. On the other hand, I never wrote a GUI app with it (Delphi is best for that).
END OF DAVID'S EMAIL
In later emails we agreed that Fortran is not used that much (there are lists of most-used languages and neither Fortran nor FORTRAN is ever in the top 10). But what intrigued me was the following contrast:
1) David says that its the BEST language for Scientific Computing. I will assume he is right.
2) I doubt much NEW code is being written in it. I will assume I am right.
So---what's up with that? Some options
OPTION 1) People SHOULD use Fortran but DON'T. If so, why is that? Fortran is not taught in schools. People are used to what they already know. Perhaps people who do pick up new things easily and want to use new things would rather use NEW things rather than NEW-TO-THEM-BUT-NOT-TO-THEIR-GRANDMOTHER things. Could be a coolness factor. Do the advantages of Fortran outweight the disadvantages? Is what they are using good enough?
OPTION 2) The amount of Scientific computing software being written is small since we already have these great Fortran packages. So it may be a victim of its own success.
CAVEAT: When I emailed David a first draft of the post he pointed out the following which has to do with the lists of most-used programming languages:
DAVIDS EMAIL:
The problem with the lists you were looking at is that most people in the world are not scientists, so most software being written is not for scientists. Scientists and technical people are writing lots of new code. If you look at a list of scientific languages, you will see Fortran, e.g., here and here.
There are several Fortran compilers available. One of the best was bought by Intel some time back and they still sell it. I doubt they would do that if no one was using it. Actually, I think Intel had a compiler, but bought the Compaq compiler (which used to be the Digital Equipment compiler) and merged the Compaq team with their team. Something like that. I was using the Compaq compiler around that time.
END OF DAVID's EMAIL
One quote from the second pointer I find intriguing. (Second use of the word intriguing. It was my word-of-the-day on my word-calendar).
... facilities for inter-operation with C were added to Fortran 2003 and enhanced by ISO/ICE technical specification 29113, which will be incorporated into Fortran 2018.
I (Bill) don't know what some of that means; however, it does mean that Fortran is still active.
One fear: with its not being taught that much, will knowledge of it die out. We be like Star Trek aliens:
The old ones built these machines, but then died and we can't fix them!
Tuesday, July 02, 2019
Local Kid Makes History
The blogosphere is blowing up over Hao Huang's just posted proof of the sensitivity conjecture, what was one of the more frustrating open questions in complexity.Huang, an assistant professor in the math department at Emory, settled an open question about the hypercube. The hypercube is a graph on N=2n vertices where each vertex corresponds to an n-bit string and their are edges between vertices corresponding to strings that differ in a single bit. Think of the set of the strings of odd parity, N/2 vertices with no edges between them. Add any other vertex and it would have n neighbors. Huang showed that no matter how you placed those N/2+1 vertices in the hypercube, some vertex will have at least n1/2 neighbors. By an old result of Gotsman and Linial, Huang's theorem implies the sensitivity conjecture.
I won't go through the shockingly simple proof, the paper is well written, or you can read the blogs I linked to above or even just Ryan O'Donnell's tweet.
I have nothing more to say than wow, just wow.
Sunday, June 30, 2019
A proof that 22/7 - pi > 0 and more
My father was a High School English teacher who did not know much math. As I was going off to college, intending to major in math, he gave me the following sage advice:
1) Take Physics as well as Math since Physics and Math go well together. This was good advice. I took the first year of Physics for Physics Majors, and I later took a senior course in Mechanics since that was my favorite part of the first year course. Kudos to Dad!
2) π is exactly 22/7. I knew this was not true, but I also knew that I had no easy way to show him this. In fact, I wonder if I could have proven it myself back then.
I had not thought about this in many years when I came across the following:
Problem A-1 on the 1968 Putnam exam:
Prove 22/7 - π = ∫01 (x4(1-x)4)/(1+ x2 )dx
(I can easily do his by partial fractions and remembering that ∫ 1/(1+x^2) dx = tan-1x which is tan inverse, not 1/tan. See here.)
(ADDED LATER---I have added conjectures on getting integrals of the form above except with 4 replaced by any natural number. Be the first on your block to solve my conjectures! It has to be easier than the Sensitivity Conjecture!)
Let n ∈ N which we will choose later. By looking at the circle that is inscribed in a regular n-polygon (n even) one finds that
n tan(π/n) > π
So we seek an even value of n such that
n tan(π/n) < 22/7
Using Wolfram alpha the smallest such n is 92.
Would that convince Dad? Would he understand it? Probably not. Oh well.
Some misc points.
1) While working on this post I originally wanted to find tan(π/27) by using the half-angle formula many times, and get an exact answer in terms of radicals, rather than using Wolfram Alpha.
a) While I have lots of combinatorics books, theory of comp books, and more Ramsey Theory books than one person should own in my house, I didn't have a SINGLE book with any trig in it.
b) I easily found it on the web:
tan(x/2) = sqrt( (1-cos x)/(1+cos x) ) = sin x/(1+cos x) = (1-cos x)/(sin x).
None of these seems like it would get me a nice expression for tan(π/27). But I don't know. Is there a nice expression for tan(π/2k) ? If you know of one then leave a polite comment.
2) I assumed that there was a more clever and faster way to do the integral. I could not find old Putnam exams and their solutions the web (I'm sure they are there someplace! --- if you know then comment politely with a pointer). So I got a book out of the library The William Lowell Putnam Mathematical Competition Problems and Solutions 1965--1984 by Alexanderson, Klosinski, and Larson. Here is the clever solution:
The standard approach from Elementary Calculus applies.
Not as clever as I as hoping for.
3) I also looked at the integral with 4 replaced by 1,2,3,4,...,16. The results are in the writeup I pointed to before. It looks like I can use this sequence to get upper and lower bound on pi, ln(2), pi+2ln(2), and pi-2ln(2). I have not proven any of this. But take a look! And as noted above I have conjectures!
4) When I looked up INSCRIBING a circle in a regular n-polygon, Google kept giving me CIRCUMSCRIBING. Why? I do not know but I can speculate. Archimedes had a very nice way of using circumscribed circles to approximate pi. Its on youtube here. Hence people are used to using circumscribed rather than inscribed circles.
Thursday, June 27, 2019
FCRC 2019
 |
| Georgia Tech FCRC Participants |
Geoff Hinton and Yann LeCun gave their Turing award lectures, their co-winner Yoshua Bengio not in attendance. Hinton talked about how machine learning triumphed over symbolic AI. LeCun argued that under uncertainty, one should learn the distribution instead of just the average. If you want more, just watch it yourself.
To get to the STOC lectures you go up and down escalators and pass through ISCA (Computer Architecture) and PLDI (Programming Languages). It's like you are going up the computing stack until you reach algorithms and complexity.
The conference center was just two blocks from Chase Field so we could take in a Diamondbacks baseball game. They opened the roof because the temperature dropped into the double digits. Last night, Paul McCartney played at an arena just a block from the conference center, but instead I hung out at an Uber reception for the EC conference.
Let me mention a best paper awardee, The Reachability Problem for Petri Nets is Not Elementary by Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki. In a Petri net you have a list of vectors of integers and an initial and final vector. You start with the initial vector and can add any of the other vectors nondeterministically as often as you like as long as no coordinate goes negative. Can you get to the final vector? This problem was known to be computable in "Ackermannian" time and EXPSPACE-hard. This paper shows the problem is not elementary, i.e. not solvable in running time a tower of 2's to the n. A recent result shows Petri Nets reachability is primitive recursive for fixed dimensions.
Avi Wigderson gave the Knuth Prize lecture exploring deep connections between mathematics and algorithms. Hopefully the video will be online soon.
STOC next year in Chicago, EC as part of the Game Theory Congress in Budapest.
Avi Wigderson gave the Knuth Prize lecture exploring deep connections between mathematics and algorithms. Hopefully the video will be online soon.
STOC next year in Chicago, EC as part of the Game Theory Congress in Budapest.
Monday, June 24, 2019
Are you smarter than a 5th grade amoeba?
(title of this blog is due to Henry Baker who posted an article about this elsewhere)
Amoeba finds approx solution to TSP in linear time:here.
Over the years we have seen models of computation that claim to solve NPC or other hard problems quickly. I ask non-rhetorically and with and open mind how they have panned out.
In no particular order:
1) Parallelism. For solving problems faster YES. For speeding up how to solve NPC problems I think YES. For making P=NP somehow NO. Even so, parallel computers have been a definite practical success.
2) Quantum Computing. Will they factor large numbers anytime soon? Ever? Should we view the effort to build them as an awesome and insightful Physics experiment? Are there any problems that they are NOW doing faster? Is Quantum Crypto (I know, not the same thing) actually used? Will other things of interest come out of the study of quantum computing? It already has, see here.
3) DNA computing. Did that lead to practical solutions to NPC problems? I do not think it did. Did that lead to interesting math? Interesting biology? Interesting science? I do not know.
4) Autistic computing for finding primes: see here. Oliver Sacks, the neurologist ,claimed that two autistic twin brothers could generate large primes quickly. This story was never put to a rigorous test and may not be quite right.
5) Amoeba computing: Too early to tell. The article seems to say it succeeded on 8 cities
The problem with all of these non-standard models of computing is SCALE. And the more powerful classic computers get, the harder it is for these nonstandard models to compete.
Are these models interesting even if they don't end up getting us fast algorithms? They can be:
1) Do they lead to mathematics of interest? (Quantum- Yes, Parallelism- Yes)
2) Did they inspire algorithms for classical computers? (Quantum- Yes)
3) Do they give insight into other fields? (Quantum for Physics yes, DNA-computing for bio-??)
4) Have they ACTUALLY sped up up computations in meaningful ways for problems we care about (Parallelism has)
If you know of any result which I missed
(e.g.,
Amoeba-computing giving insight into evolution,
Autistic computing being used by the NSA to find primes,
DNA computing leading to interesting mathematics)
then leave polite comments!
Amoeba finds approx solution to TSP in linear time:here.
Over the years we have seen models of computation that claim to solve NPC or other hard problems quickly. I ask non-rhetorically and with and open mind how they have panned out.
In no particular order:
1) Parallelism. For solving problems faster YES. For speeding up how to solve NPC problems I think YES. For making P=NP somehow NO. Even so, parallel computers have been a definite practical success.
2) Quantum Computing. Will they factor large numbers anytime soon? Ever? Should we view the effort to build them as an awesome and insightful Physics experiment? Are there any problems that they are NOW doing faster? Is Quantum Crypto (I know, not the same thing) actually used? Will other things of interest come out of the study of quantum computing? It already has, see here.
3) DNA computing. Did that lead to practical solutions to NPC problems? I do not think it did. Did that lead to interesting math? Interesting biology? Interesting science? I do not know.
4) Autistic computing for finding primes: see here. Oliver Sacks, the neurologist ,claimed that two autistic twin brothers could generate large primes quickly. This story was never put to a rigorous test and may not be quite right.
5) Amoeba computing: Too early to tell. The article seems to say it succeeded on 8 cities
The problem with all of these non-standard models of computing is SCALE. And the more powerful classic computers get, the harder it is for these nonstandard models to compete.
Are these models interesting even if they don't end up getting us fast algorithms? They can be:
1) Do they lead to mathematics of interest? (Quantum- Yes, Parallelism- Yes)
2) Did they inspire algorithms for classical computers? (Quantum- Yes)
3) Do they give insight into other fields? (Quantum for Physics yes, DNA-computing for bio-??)
4) Have they ACTUALLY sped up up computations in meaningful ways for problems we care about (Parallelism has)
If you know of any result which I missed
(e.g.,
Amoeba-computing giving insight into evolution,
Autistic computing being used by the NSA to find primes,
DNA computing leading to interesting mathematics)
then leave polite comments!
Subscribe to:
Posts (Atom)