Lance Fortnow's Blog, page 125

Are most lower bounds really upper bounds?

Recently Daniel Apon (grad student of Jon Katz at UMCP, but he also hangs out with me) proved a LOWER BOUND by proving an UPPER BOUND. His paper is here. I have heard it said (I think by Avi W and Lane H) that MOST lower bounds are really upper bounds. Below I use the term Non-Alg Lower Bound for a lower bound that is NOT an algorithm. This is not a rigorous notion and the items below are up for debate.



Time Hier, Space Hier- Diagonalization. I would call that Non-Alg.

Cooks Theorem: this is an ALGORITHM to transform a Non Det TM and a string x to a Boolean Formula.

All reductions can be viewed as ALGORITHMS.

Parity not in AC0: The Yao-Hastad proof can be viewed as a non-alg lower bound for the depth 1 or 2, and then a randomized ALGORITHM to transform depth d to depth d-1.

Parity not in AC0[3]: This is a Non-Alg lower bounds--- you show that parity has some property (not being able to be approx by low degree polys) and then you show that AC0[3] cannot deal with this property.

Comm Complexity: The det lower bound on EQ is a Non-Alg lower bound. I think the randomized lower bound on DISJOINT is a Non-Alg lower bounds. Many others lower bounds are reductions to these two, and hence are algorithms.

Multiparty Comm Comp: I'll just mention one result: Chandra-Furst-Lipton's lower bounds on EXACT-N for k-player Number-on-Forehead. The lower bounds shows that if there is a protocol of t bits then some structure can be colored in a certain way. Then Ramsey Theory is used. Non-Alg Lower bound I think.

Decision Tree Complexity (Comparisons): The lower bounds on SORTING and MAX, are non-Alg lower bounds. The following leave-counting lower bound for

2nd largest is sort-of a reduction to MAX but I still think its non-alg: First note that the lower bound for MAX is very strong- even the best case

requires n-1 comps. Hence any DT for MAX has roughly 2n-1 leaves.

T is a DT for 2nd largest. For all i=1,...,n let Ti be the subtree where xi WINS. This is a MAX tree for n-1 elements so has 2n-2 leaves. All these sets of leaves are disjoint so T has n2n-2 leaves.Hence T has height n+ log n + \Omega(1).)

Decision Tree Complexity (Other queries): Algebraic Queries, k-ary queries have all been studied.

The Algebraic Queries lower bounds use number-of-component arguments and seem non-alg. Some of the k-ary query lower bounds use Ramsey Theory to reduce to the comparison case.

Branching programs and other models often reduce to comm complexity. Is that an algorithm.

Ryan Williams proof that NEXP is not in ACC is really, at its core, an algorithm that does slightly better than brute force.



My Final Opinion: The above is a random sample, but it seems to be that there are plenty of lower bounds that are non-alg lower bounds. However, as more and more lower bounds are known, more and more reductions will be used and hence there will be more algorithms.

Beauty and Science

Christopher Shea wrote a recent Chronicle Review article Is Scientific Truth Always Beautiful? I would argue the answer is yes, and it boils down to Occam's Razor that the simplest explanation that fits the available data is typically the best and there is a strong relationship between beauty and simplicity.



An ugly scientific theory would have a large number of parameters which will lead, in computer science terms, to overfitting the current state of the world and almost surely such a theory would be incorrect. So every scientific truth should be beautiful.



Now the converse doesn't hold. There are far more beautiful theories than correct ones. That's the beauty of the scientific method to help sort them out. As Einstein may have said, "Everything should be kept as simple as possible, but no simpler."



In mathematics, not all correct proofs are beautiful and not all beautiful proofs are correct. But if you believe Erdős, all correct theorems have beautiful proofs, all kept in The Book.

The Complexity-STOC Bonanza

STOC and Complexity are co-located this July in beautiful Palo Alto, California. Both conferences have just announced their accepted papers: STOC (with PDF links) and Complexity.



Both conferences will have student travel awards. Details coming soon to the respective web sites.



On a different topic, The 2014 Nevanlinna Prize committee is still accepting nomination until May 1, 2013.

Proving DFA-langs closed under concat and * without using equiv to NDFA's

While teaching the Equiv of DFA, NDFA, Reg exps, I wanted to impress upon my students that the best way to show DFA-langs are closed under concat and * is to first prove DFA=NDFA and then show NDFA's closed under concat and * (which is easy). The question arises: CAN one PROVE that DFA-langs are closed under concat and star without using the equivalence to NDFA's? I emailed this informal question to Richard Beigel (my go-to guy for formal lang theory--- its a good thing he's not my go-to guy for Prog Langs since then I couldn't use go-to's.)



He emailed back the following sketches of proofs of closure that only use DFA's:



Closure under concat: states will be of the form (q,S) where q is a state of M1 and S is a set of states of M2. Start in (q0, {}) where q0 is the start state of M1. Each time a character is read advance q in M1 and advance each element of S in M2. Whenever q is an accepting state, insert M2's start set into S. Accept if S contains an accepting state of M2.



Closure under star: It is easy to modify a DFA so that the start state has no incoming edges. I'll assume that M is already in that form. State of the new machine will be a set S of states of M. Start in state {q0}. Each time a character is read, advance each state in S and then if S contains an accepting state of M insert q0 into S. Accept if S contains q0.



After complementing him on his answes I asked him him about proving Reg-exp-langs closed under complementation without using equiv to DFA's. He doesn't know how to do that, so I assume it can't be done. But is there a rigorous way to even state that?

~

Postdocs in Computer Science

Anita Jones is troubled by the growing number of postdocs in computer science, she uses "troubling" twice in the first paragraph of her CACM Viewpoint. But is it really a troubling trend or just a natural outgrowth of a maturing field?



Theoretical computer science leads computer science in having and even embracing a postdoc culture. Nearly every graduating PhD in theoretical computer science that remains in academia takes a postdoc position before taking an tenure-track job. If anything I hear theorists lamenting a drop in theory postdocs this year with the end of the Simons postdocs and CI fellows.



Postdocs give PhDs a chance to focus on research and strengthen them for the future job market. I initially started as a two-year assistant professor at Chicago, basically a teaching postdoc. If I didn't have that opportunity my research career would have died in its tracks.



What would happen if all postdoc funding was stopped. That would lead to more funding for graduate students most of whom would have to take a non-research career especially with no postdoc positions available. Hard to see how anyone wins.



Anita and I both agree that a successful postdoc experience requires strong mentorship and inclusiveness or otherwise the postdoc is just working in a vacuum. The CRA has put out a best practices memo, worth reading for both postdocs and the people who hire them.

The (il)logic of fandom

(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research. If you are an ugrad, go to that site and see if you want to apply. If you are a faculty see if you want to recommend it to some students. Deadline to apply is Feb 15.)



The Sunday before the Superbowl I spotted this curious passage in THE WASHINGTON POST which I paraphrase.

Washington Redskins fans should root for the Baltimore Ravens in the Superbowl because the two teams share many fine qualities. Both have gritty defense, soft-spoken by shrewd head coaches, underrated quarterbacks craving validation on the big stage. Neither team is flashy or has big starts--- rather they are both greater than the sum of their parts.

I interpret this as assuming Sports fans pick who to root for in a logical manner. Something like I like quality X, this team has quality X, so I will root for them. Is that how sports fans act. If it was then sports fans would change who they root for often. They do not.



So what is the logic behind fandom? Why do people root for certain teams, likely for a lifetime. Is it rational?



Root root root for the home team, for it they don't win its a shame. Root for the team in the place you live NOW.

Root for your childhood team. I wonder if the Chicago Cubs has more fans across the country since one of the early cable channels WGN, is from Chicago and (I think) carries Cubs games--- so you can be a transplanted Chicagoan and still watch your team. As people move around alot loyalty to your home team may fade.

For College teams its common to root for the team that comes from the college you went to. This is less true for graduate school.

Fair weather fans root for the team that's winning. But it is more common to have a team (perhaps your home team) that you ignore unless they are winning. So you don't choose your team based on this, but you choose weather to care based on this.

The early NY Mets (early 1960's) were a terrible team but they had lots of fans. There was a loser-chic factor. The Chicago Cubs have also had that. This is rare or even nonexistent now. Everyone loves a winner.

Individual players may appeal to you. Tim Teabow got some attention because of his devout Christianity. But this is rare. Its more common to get attention for negative behavior. This is more a matter of rooting for a person rather than the team.

A while back some teams delayed getting any black players on them so they would still appeal to racist fans. This stopped once such teams just lost too much since they were not using that talent pool. Might someone root for or against a team because of the attitude or politics of the management? If some team took the profits and funded alternative energy for real would you root for them? What if they funded Ramsey Theory? What if they supported Same Sex marriage? I doubt a team would have a public opinion on an issue which may cause them to lose fans, though a player might.

A friend of yours is ON the team so you root for the team and your friend. This is rare. But if someone on the team is from your SCHOOL- you may have a certain affinity for that person and team even if you don't know them. Whenever I hear that some pro football player is from Harvard (where I went to graduate school) I at least notice this. Its rare.

In the Olympics one usually roots for their own country. What if (say) American offered the top Tennis player in the world (who was not an American) to become a citizen of the USA (and pay him for it) then he won the Gold Medal for American. (I think this is legal.) Would Americans be proud of that or feel that's not quite right? I suspect that this kind of thing will happen more often over time. While this may seem strange it already happens within a country. The NY Mets do not have more players from NY. Nor do the Baltimore Ravens have more players from Baltimore.

Jerry Seinfeld once commented that we LOVE this player if he's on OUR team but HATE him if he is on another team. What has changed? His uniform. So we are rooting for clothing.



Is there a logic to who a fan roots for or not? Is there a logic to being a sports fan?

Who do you write papers for?

Mitch Daniels, the former governor of Indiana and new president of Purdue, wrote an inaugural letter where he discusses many of the challenges of higher education. His lists several common attacks on universities and one caught my eye.

Too many professors are spending too much time "writing papers for each other," researching abstruse topics of no real utility and no real incremental contribution to human knowledge or understanding.

I write papers mainly for myself. I have my own opinions on what problems are important and where my interests and research strengths lie. One of the main draws of being a professor is having the freedom to choose our own research.



But we have to write for our peers as well. It's our peers that review and cite our papers and make decisions about grants and jobs. For the most part our peers are the only ones who read our papers.



In the end we write papers for society. Most of our papers taken individually add a small amount to human knowledge and are only of interest to fellow specialists. But taken together our research drives a field of inquiry allowing us to understand and take on new challenges. Even if we have trouble selling a specific theoretical computer science papers to a broader audience, taken as a whole theory helps us model and understand the power of computation and leads to smarter and faster algorithms on real world machines.

TCS online series- could this work?

Oded Regev, Anindya De and Thomas Vidick we are about to start an online TCS seminar series. See here for details, though I have the first few paragraphs below.



Its an interesting idea- we can't all get to conferences so this is a good way to get information out there. Wave of the future? We'll see how it goes.



Here is the first few paragraphs:



Ever wished you could attend that talk if only you didn't have to hike the Rockies, or swim across the Atlantic, to get there; if only it could have been scheduled the following week, because this week is finals; if only you could watch it from your desk, or for that matter directly from your bed?



Starting this semester TCS+ will solve all your worries. We are delighted to announce the initiation of a new series of *online* seminars in theoretical computer science. The seminars will be run using the hangout feature of Google+. The speaker and slides will be broadcast live as well as recorded and made available online. Anyone with a computer (and a decent browser) can watch; anyone with a webcam can join the live audience and participate.



Our goal is to make engaging talks accessible to the widest possible audience, ensuring a carbon-free dissemination of ideas across the globe.



We're still in beta, and we welcome any feedback from the community. There will undoubtedly be glitches at first, but we hope you'll bear with us and be as excited as we are at trying out the possibilities of this new medium.



Now for some more practical information:



Inauguration talk:

Speaker: Ronald de Wolf, CWI, Amsterdam.

Title: Exponential Lower Bounds for Polytopes in Combinatorial Optimization.

Source: Paper of the same name from STOC12 with Samuel Fiorini, Serge Massar,

Sebastian Pokutta and Hans Raj Tiwary that won the best paper award.)

The End of a Useless Test

First a word from our sponsor: Mihalis Yannakakis is celebrating his 60th birthday this year and you are invited to the party.



From the Educational Testing Service:

The last administration of the GRE Computer Science Test will be in April 2013. The test will be discontinued after the April 2013 administration. Scores will continue to be reportable for five years.

Why is the Computer Science Test being discontinued?

Over the last several years, the number of individuals taking the Computer Science Test has declined significantly. Test volume will soon reach a point where ETS can no longer support the test psychometrically. As a result, the GRE Program has decided to discontinue the Computer Science Test. The test will be offered for the last time in April 2013

"Pyschometrically" just refers to the ability to measure abilities, mental traits and processes. Seems redundant in this context.



Bill tells me Maryland CS used to require a subject GRE but no longer does. Georgia Tech CS does not require a GRE. We have a separate PhD program in Algorithms, Combinatorics and Optimization that requires the math subject test.



Computer Science is a broad field and can't be easily tested, psychometrically or otherwise, and the score of the subject test does not help us determine who will be a good grad student.



The math test is not much better because the applicants we care about in theory generally get a perfect score or very close to it.



The regular GRE exam is not that much better. The quantitative can only help weed the weak students. The analytic score should be a good predictor but isn't. The verbal score, at least among Americans, oddly enough may have the best correlation to success in grad school, but not reliable enough to put much weight on it.



So how do I judge PhD candidates? Grades in CS and math courses taking into account the quality of the university, any undergraduate research, and the recommendation letters.

A New application of Ramsey Theory to a Geometry problem

All of the material summazized here is in a new paper by Gasarch and Zbarsky. You can find that paper here)



Consider the following problem:




Let {p1,...,pn} be a subset of distinct points in Rd. We think of d ≤ n. How big is the largest subset X of points such that all of the distances determined by pairs of elements of X are different? Let h(d,n) be the min size of X. That is, we always have a set X of size h(d,n) with all distances between points different.


Assume that no three of the original points are collinear. How big is the largest subset X of points such that all of the areas determined by triples of points in X are different? Let g(d,n) be the min size of X. That is, we always have a set X of size g(d,n) with all triangle-areas of different sizes.



(This is NOT the Erdos Distance problem where you are given n points and want to know the min number of diff distances you have.) What is know about the problem posed?


The case of d=1 is known h(1,n)=Θ(sqrt(n)).


Erdos said somewhat mysterioulsy (I paraphrase)

It is easy to see that there are constants ep(d) such that h(d) ≥ nep(d). (BILL: Frankly- I do not find it easy to see.)

Aside from that, not much was known.



Until now. Gasarch and Zbarsky have shown the following (roughly)


h(d,n) ≥ Ω(n1/(6d)).


g(2,n) ≥ Ω((log log n)1/2901).


g(3,n) ≥ Ω((log log n)1/27804).





We believe these results are new. They were obtained using variants of the Canonical Ramsey Theorem, originally due to Erdos and Rado, and some geometric lemmas.