Thursday, June 06, 2013

Complexity Typecast

Lance: Welcome to another exciting typecast coming from sunny Stanford University. I'm with Bill at the 28th Conference on Computational Complexity. Hi Bill, I see you're now at Mizzou.

Bill: Yes, my name tag says Univ. of Missouri but the body is still at Maryland. But Missouri is the Show-Me State and I don't believe theorems until you show me the proof.

Lance: Interesting name tags going around. Joshua Brody is at the University of Aarhus in Windsor, Vermont. But outside the name tags, this has been a well-run meeting.

Bill: Indeed. So Lance, anything seem different this year.

Lance: I'm noticing a few trends at both STOC and Complexity. Both have strong attendance this year, especially for West Coast meetings, and more papers than usual. Though fewer women attendees and I'm not sure why.

Bill: I was at a computability meeting at Iowa recently where there six women but they were the same six women from twenty years ago. That does not bode for the future.

Lance: I think that says more about computability as I'm guessing all the attendees were there twenty years ago.

Bill: I resemble that remark. Let's talk math. At one you were a Kolmogorov skeptic, now you are a believer.

Lance: Yes once I actually used it for a theorem I saw the light.

Bill: Speaking of light, are you now a quantum believer? Ronald de Wolf gave an awesome talk on the applications of quantum techniques to classical theorems. Were you convinced?

Lance: There are times that thinking quantumly can help generate good theorems. Nice to see quantum is good for something.

Bill: They didn't have quantum back in the days of the first complexity conference in 1986.

Lance: Yes the world was classical back then, just like the world was flat in 1400. No one here remembers that complexity meeting in 1400 but I have seen a few people from the original 1986 meeting.

Bill: Besides us, Eric Allender, Jonathan Buss, Steve Homer and Osamu Watanabe. Whether we remember anything from those days...

Lance: I remember meeting you for the first time. I was just a first-year grad student and I walked into a room with you and David Barrington talking at light speed. I thought you were both so smart.

Bill: Sorry to disappoint you. So Eric is the last man standing?

Lance: Yes, since I missed complexity last year, Eric Allender is the only person to have attended all 28 Complexity meetings. He does not want that to be his claim to fame.

Bill: Back in '86 I could follow 2/3 of 3/4 of the talks. Now I can follow 1/8 of 1/4 of all the talk. Have I gotten dumber or have the talks gotten harder?

Lance: Yes.

Bill: Thank you Lance, how about you?

Lance: Yes. More the techniques are quite different than the more computability type tools we used back in the day.

Bill: A field must change or die. I'm glad we're changing unlike certain areas of math I will not mention.

Lance: Speaking of change...

Bill: There are 242 ways of changing a dollar into pennies, nickels, dimes and quarters.

Lance: I did not know that! Moving on, what do you think of Joan Feigenbaum's suggestions on changing STOC?

Bill: I'll do a blog post on this later, but I'm generally in favor of more people on the PC (2-tiered), more papers in conference (3 parallel sessions) and more workshops, invited papers and posters.

Lance: So Bill ready to wrap it up?

Bill: Yes, it's time.

Lance: So remember, in a complex world best to keep it simple. And buy my book.

6 comments:

  1. With half-dollars included, there are 293 ways to make change for one dollar:
    -----
    (1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)//
      Series[(1/#),{x,0,100}]&//Normal//
       Coefficient[#,x^100]&//Timing//Print;
    -----

    ReplyDelete
    Replies
    1. I think you also assume a dollar coin in your counting there.

      Delete
  2. Nice problem, Bill!

    Octave code to test different input combinations:

    coins = [1 5 10 25];
    total_amount = 100;

    coins = reshape( sort( coins, 'ascend' ), 1, [] );

    num_configurations = zeros( total_amount, length( coins ) );

    for cur_total = 1 : total_amount;
      cur_configurations = 0;
      for cur_coini = 1 : length( coins );
        cur_coin = coins( cur_coini );
        if cur_total == cur_coin;
          cur_configurations = cur_configurations + 1;
        elseif cur_total > cur_coin;
          cur_configurations = cur_configurations + num_configurations( cur_total - cur_coin, cur_coini );
        end
        num_configurations( cur_total, cur_coini ) = cur_configurations;
      end
    end

    fprintf( '%d %d\n', [ 1 :  total_amount; num_configurations( :, end )' ] );

    ReplyDelete
    Replies
    1. Slightly modified to allow switching between smallest configuration and total number of configurations (could not resist the temptation to go one-up on J. Sidles's solution :-))

      coins = [1 5 10 25];
      % coins = [1 3 5 7 11 13 17 19];
      total_amount = 100;

      min_coins = 1;  % 0 for number of possible configurations, 1 for number of coins in smallest configuration

      coins = sort( coins, 'ascend' );

      num_configurations = zeros( total_amount, length( coins ) );

      for cur_total = 1 : total_amount;
        if min_coins;
          cur_configurations = inf;
        else
          cur_configurations = 0;
        end
        for cur_coini = 1 : length( coins );
          cur_coin = coins( cur_coini );
          if cur_total == cur_coin;
            if min_coins;
              cur_configurations = 1;
            else
              cur_configurations = cur_configurations + 1;
            end
          elseif cur_total > cur_coin;
            if min_coins;
              cur_configurations = min( [ cur_configurations,  num_configurations( cur_total - cur_coin, cur_coini ) + 1 ] );
            else
              cur_configurations = cur_configurations + num_configurations( cur_total - cur_coin, cur_coini );
            end
          end
          num_configurations( cur_total, cur_coini ) = cur_configurations;
        end
      end

      fprintf( '%d %d\n', [ 1 :  total_amount; num_configurations( :, end )' ] );

      Delete
  3. Every CCC I've attended has had about the same women attendance: very, very low :-/
    (OK, I do read the blog sometimes...)

    ReplyDelete