Counting Descriptions- a ``new'' complexity class

Let n_σ(w) is the number of σ's in w.

We often ask our students about languages like { w | n_a(w) = 2n_b(w) } (CFL but not REG). Lets formally define languages that are like that.

A COUNTING DESCRIPTION is a boolean combination of linear equations and inequalities involving n_σ(w). For example

(n_a(w) ≤ 2n_b(w)+3) AND NOT( n_c(w) = n_b(w) ).

We denote a counting description by E. Let L(E) = { w : E(w) is true } A lang L is CD if there exists an E such that L=L(E). What to make of the class CD?

The following items came out of emails between myself and Eric Allender, Dave Barrington, and Neil Immerman.

1. CD is contained in 1-way log space and in uniform TC₀.
   
2. CD is incomparable to REG since (1) from above we see there are langs in CD that are not REG, and (2) ba^* is not in CD.
   
3. CD intersect REG is in uniform AC₀
   
4. Parikh's Theorem yields a large class of CD's that produce context free languages.
   
5. If E is a Boolean combination of threshold and mod statement, each about a single n_σ(w), then L(E) is regular
   
6. The following papers may help answer some of the questions one could ask: here and here.
   

Are the following decidable:

1. Given a counting description E, is L(E) regular?
   
2. Given a counting description E, is L(E) context free?
   

Richard Beigel has shown these problems, with an unbounded alphabet size, are NP-hard. see here. I am very curious about the case where the alphabet size is bounded. Are there other (NATURAL!) classes one could ask about? NOT context sensitive since CSL contain log space. NOT the class DSPACE((log n)^1/2) since that's not natural. Maybe some sublinear class would be interesting. We can also ask variants of these questions involving any combinations of the following variants:

1. Do not allow negation.
   
2. Do not allow intersection.
   
3. Do not allow inequalities.
   
4. Do not allow additive constants.
   
5. Do not allow multiplicative constants.
   
6. Only allow a bounded alphabet size.
   
7. Allow other types of equations, for example n_a(w) = n_b(w)².
   
8. Allow other primitives such ast n_a(w) == n_b(w) mod 9.
   
9. Have a non-uniform version of Counting Descriptions and bound the size of the formula as a function of n.
   

In problem 7 if you allow any poly then the problem is undecidable by the solution to Hilbert's tenth problem.

A Century of Erdős

The great Hungarian combinatorialist Paul Erdős was born one hundred years ago today. The big celebration will happen in Budapest in July.

It's hard to say more about Erdős than I've already said in this blog so let's recap some of those highlights.

• What is your Erdős number?
• The Erdős-de Bruijn Theorem
• The Erdős distance problem solved
• Erdős-Szekeres monotone sequence theorem
• Erdős-Rado sunflower theorem
• Erdős-Turan conjecture
• Erdős and the "stupid question"
• Solving math problems for money
• Sum-Product Theorems
• Sauer's Lemma (which may or may not have been first conjectured by Erdős)

Shiva also celebrates the centenary of Erdős and I second his suggestion to check out The Man Who Loved Only Numbers, Paul Hoffman's great biography about his life. 

The Slot Machine Theory of Paper Submissions

Why do scientists publish so much? There is the whole "publish or perish" thing but that doesn't explain the large increase in quantity of publications. With a focus on important publications and measures like H-indices, a simple publication in a conference often won't help someone's career. Yet we continue to publish as much as we can. Why?

When you play a slot machine and you win, you get lights, music, sounds of coins coming out of the machine. If you lose, nothing. Lots of positive feedback if you win with no negative feedback if you don't.

If you submit a paper and it gets accepted into a conference, you feel excited. Excited to see your name on the list of accepted papers. Excited to update your CV and to give that talk or poster that only those few who's paper was accepted get to give.

If your paper is rejected, nothing. You don't list rejected papers on your CV. Nobody will even know you submitted the paper. And you can just take that paper and submit it to another conference. Lots of positive feedback if your paper is accepted with no negative feedback if it isn't.

Some people might argue the analogy doesn't work since slot machines are arbitrary and random. Those people have never seen a program committee in action.

Will they use EasyPope to pick the Pope in 2050?

AP press 2050: The new pope was elected in just 2 hours using EasyPope, the software based on EasyChair, software designed to deciding which papers get into a conference. The new Pope was quoted as saying How did they manage in the old days actually Flying to Vatican to elect someone. This just seems silly.

(I do not know which is more unrealistic: That the Pope will be picked this way or that there will be an AP press in 2050.)

The recent Papal election was done the old fashioned way--- in person. Could they have done it over the web? Perhaps each Cardinal gives each cardinal (except themselves) a number between 1 and 10 for how good they would be, and a number between 1 and 3 for how confident they are in their vote.
Or a more complex system like e-harmony uses?

I doubt this will change anytime soon, and I doubt that it should. So what are the PROS of each way to meet? Some of this was covered in the Net vs Jet discussion.

PROS of meeting in person:

1. With current technology (and this may change) its easier to have a back and fourth in person. Even now this is possible with teleconferencing, though I wonder if this would work with the 115 cardinals.
   
2. You can read peoples faces and enthusiasm.
   
3. There are things that can come up and be discussed that you may not have thought of if you were just alone at your computer.
   
4. Technology fails sometimes.
   
5. Time limited- really has to end (Papal Elections can go on for a while; however, one of the reasons for the Papal Enclave is to FORCE them to get a Pope relatively soon.)
   
6. Builds connections. Recall the famous quote:
   

   As a society we are gaining efficiency but loosing connectivity
   

7. The meeting gives you a global view of the issues.
   

PROS of meeting just on line.

1. Money and Time are saved.
   
2. Environmental concerns of flying
   
3. Less likely to have Group Think set in.
   

So- which types of meetings are better for which events? And what is the criteria? Is the goal to have a better decision in the end? This is only one goal- the connections formed at the meeting are valuable also.

1. Papal Election. There are so many candidates and so many issues that I think in person is better. I also think it won't change--- NOT because the Vatican is Tech-Shy (the last Pope had a Twitter account) but for the reasons above.
   
2. The Maryland Math Competition. We used to meet four times a year, then two, and now its down to zero--- its all online now. We will go back to two meetings a year--- having someone explain a problem and its solution to you is much better than email. Note that for this a meeting is a time sink but not a money sink. A Memory--- my first year on the committee we met at the end for Pizza and Beer and they got me a non-alcoholic beer (since they knew I didn't drink). They were welcoming me into the club. By contrast I don't even know whose on the committee anymore---- just their email addresses.
   
3. Program Committees- The money and time involved in getting everyone to the same place is rather a lot so I suspect these will be mostly online. I know there are some exceptions, and some meetings of subsets of the committee. At one time the COLT meeting was held AT the STOC conference where everyone would be there. Even so, it seems like the advantages of in-person are out weighted by the time and money.
   
4. Conferences themselves. Could all be videotaped an available (some are) but somehow its hard for me to really GOTO an online talk.
   
5. Faculty meetings. Sometimes when we try to resolve an issue online the emails just go on forever. Best to just meet and get it over with.
   
6. Grad Admissions. Its now online. I miss the days when we would meet with paper folders in front of us and order a pizza.
   

Goodbye Old Friends

We had two terrible losses this week. Not people but websites, Intrade and Google Reader.

The corporate auditors for the real-money Irish prediction markets site Intrade found improprieties with payments to the late founder John Delaney and have effectively shut down the site, probably for good. I never bet money on Intrade but they made their bet data easily available. I used Intrade data to power my electoral markets map, possibly the most accurate predictor of elections, at least until Nate Silver came along. Even then our map updated in real time based on new information reflected in market prices, while Nate had to wait for poll data. I also used Intrade generated graphs of prediction market prices in dozens of talks I've given over the past decade. There are other sites for prediction aggregation but painful to lose the granddaddy of them all.

Google announced it is closing down Google Reader, Google's newsreader on July 1. I find Reader invaluable for keeping up with the theory blogs, especially those that don't post that often (I'm looking at you Scott and Luca) as well as a various collection of other blogs and my daily Dilbert. Not to mention the 2241 people who subscribe to this blog on Google Reader. There are alternatives (I'm trying Feedly) and I will be more vigilant on sharing posts on Twitter and Google+ but the real question is to why do fewer people use Google Reader. Is the flood of stuff on the Internet gotten so large we don't even try to keep up with it?

Turing Award to Shafi and Silvio

The 2012 ACM Turing Award, the highest honor in computer science, will be given to MIT cryptographers Shafi Goldwasser and Silvio Micali. From the press release:

Working together, they pioneered the field of provable security, which laid the mathematical foundations that made modern cryptography possible. By formalizing the concept that cryptographic security had to be computational rather than absolute, they created mathematical structures that turned cryptography from an art into a science. Their work addresses important practical problems such as the protection of data from being viewed or modified, providing a secure means of communications and transactions over the Internet. Their advances led to the notion of interactive and probabalistic proofs and had a profound impact on computational complexity, an area that focuses on classifying computational problems according to their inherent difficulty.

Shafi and Silvio's paper Probabilistic Encrytion really did set the stage for modern cryptography. Their paper with Charlie Rackoff, The Knowledge Complexity of Interactive Proof Systems started my own research in that area. When I did my graduate work at MIT, I had many great discussions with Shafi and Silvio about cryptography and proof systems and I owe them much for my own research career.

Congrats to Shafi and Silvio!

What if they gave an exam and nobody came?

A professor tells the class that he will use the highest grade to set the curve. The students all conspire to NOT take the exam, so the highest score is 0, so they should all get A's. If you were the prof what would you do?

This is NOT hypothetical. It happened- see here.

1. The prof gave all A's and didn't even mind it since the students learned to cooperate.
   
2. The prof then changed his grading scheme.
   
3. The article calls it a prisoners dilemma problem. I don't think thats right; however, it is the case that someone could have `defected'
   
4. Curving an exam based on the BEST student seems odd.
   

Opera and MOOCS

I've really learned to enjoy opera (the art form not the browser) and while I've come to really enjoy Atlanta, the city only has a regional opera company. So I tried out the Metropolitan Opera HD broadcasts in a local movie theater here. I have to say the experience was quite amazing, the picture and sound was amazing. In many ways a better experience than watching the opera live at the Met, with close-ups and back stage interviews. It doesn't replicate the atmosphere of seeing an opera live but it does give people who don't have access to the Met a great opera experience.

Watching the opera made me think of an analogy to MOOCs. There is limited scaling we can do in a classroom or an opera house, but the Opera HD and MOOCs can scale tremendously with only moderate additional cost. A MOOC doesn't replicate the classroom experience but done well it can offer some advantages to a classroom.

So this seems like a win for the opera lover. But not every opera company benefits. I went to see the Parsifal on Met HD last Saturday instead of the Altanta Opera's Traviata. Even other great US opera companies like the Chicago Lyric might not get a huge audience if they tried broadcasting their operas in movie theaters. How does the analogy play out for universities and MOOCs?

Do we ever NEED the adv pumping lemma for Reg langs?

Recall the Pumping Lemma and the Advanced Pumping Lemma for Regular languages:

Pump. Lemma: If L is regular and infinite then there exists n such that
for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, w=xyz, such that
for all i≥ 0 xyⁱz ∈ L.

Adv. Pump. Lemma: If L is regular and infinite then there exists n such that
for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, AND |xz|≤ n,
w=xyz, such that for all i≥ 0 xyⁱz ∈ L.

The only difference is the bound on |xz|.

The question arises: Do you ever need the advanced pumping Lemma?
I will phrase this question rigorously.

One common way to prove that a lang is not regular is to use the pumping lemma.
Another common way is to use closure properties: To show that some L is not regular
show that L ∩ R where R is a known regular language, is not regular.
The proof that L ∩ R may be by the pumping lemma or by a further reduction.
Other closure properties may be used to.

If L is regular and f is a function from Σ to &Sigma^*;, extend f to be on &Sigma^*;
(f(xy)=f(x)f(y), then f(L) is regular. We denote this HOM for Homomorphism.

Given a language L in alphabet Σ we define a hierarchy over L.
Each level is a set of languages.

B(0) = {L} union EVERY regular language over Σ.

If L1, L2 are in B(i) then the following are in B(i+1):

1. L1 ∩ L2, L1 ∪ L2, COMP(L1), L1^*, CONCAT(L1,L_2).
   
   
2. L1^R = { w | w ∈ L1 } where w^R is w written backwards.
   
   
3. For every f, a function from Σ to &Sigma^*;, extend f to &Sigma^*; via
   f(xy)=f(x)f(y). Put f(L1) into B(i+1).
   

Let B(ω) = B(0) ∪ B(1) ∪ ...

RIGOROUS QUESTION 1: Is there a non regular language L such that
EVERY language in B(ω) satisfies the conclusion of the Pumping Lemma.

RIGOROUS QUESTION 2: Is there a non regular language L such that
EVERY language in B(ω) satisfies the conclusion of the Adv Pumping Lemma.

RIGOROUS QUESTION 3: Are there languages L such that, for all i, B(i) is a proper subset of B(i+1)?

RIGOROUS QUESTION 4: TRUE or FALSE: For all i there exists L such that the hierarchy is proper on the first
i levels but then collapses down to the ith level.

RIGOROUS QUESTION 5: TRUE or FALSE: For all i there exists L such that the first level where
a lang appears that DOES NOT satisfy the conclusion of Pump Lemma occurs on level i.

RIGOROUS QUESTION 6: TRUE or FALSE: For all i there exists L such that the first level where
a lang appears that DOES NOT satisfy the conclusion of Adv Pump Lemma occurs on level i.

A lang satisfying Q1 that could be proven non-reg with adv pumping lemma
(possibly with closure stuff) would be interesting in that it would be a case
where you NEED Adv Pumping Lemma.

A lang satisfying Q2 that could be proven non-reg with adv pumping lemma
(possibly with closure stuff) would be interesting in that it would lead to
other techniques to show langs not regular (such techniques may already
be known- the Myhill-Nerode Theorem may be one of them).