Instructor: Lane A. Hemaspaandra
TA: Adam Sadilek
Note that even if you do the above things, sometimes browsers hold things without rechecking them. This most typically happens on things such as postscript documents called by links from web pages (even when it knows to recheck the web page each time, a browser may be too lazy to do that for files in its cache). If you have problems with that, simply emptying your cache should get you the fresh version of the object. Note that in Netscape/Mozilla/Firefox, if you find that it seems not to be grabbing the most current version of a web page (and on some browsers, using the forward/back buttons evades even the most emphatic preference settings), it often helps to simply use Shift-[ReloadButton] to tell it, "Go check again."
Disclaimer: Hey, I'm a theory professor, so I'm probably the worst person imaginable to take advice from on taming your browser.
P.S. A bit of additional browser help, from a Firefox fan:
[Here is] how to tune cache settings for Firefox. The following steps are used do it: 1) Type "about:config" (without quotes) in URL bar, press ENTER, 2) Find key "browser.cache.check_doc_frequency", 3) Change value to "1", which means "Check every time I view the page". That should do it. The default is "3 (default): Check when the page is out of date (automatically determined)", but that does not always work.
By the way, regarding yesterday's lecture, don't be worried if it was too technical for you to follow closely (although I did include above a copy of the actual technical paper, in case you want to look that over, and I do hope you got the general flavor of what the work had shown, namely, (a) Comparing power indices is computationally complex, and (b) the Shapley-Shubik (SS) power index is #P-complete even with respect to a more restrictive reduction type than was previously known). It was an actual talk direct from a real, technical conference attended by, basically, lots of professors and some graduate students, and I was giving it as an example of what an actual technical conference talk looks like. (If I give a second research guest talk myself, it will be a very different type of talk: One based on a 1-hour seminar talk, which is aimed at a far broader audience.)
@InCollection{fra-sob:b:bingo,
author = {M. Sobel and K. Frankowski},
title = {Venn Diagrams, Coupon Collections,
Bingo games, and Dirichlet Distributions},
booktitle = {Advances in Statistical Decision Theory
and Applications},
pages = {343--367},
publisher = {Birkhauser Boston},
year = 1997,
editor = {S. Panchapakesan and N. Balakrishnan},
chapter = 23,
Keywords = "bingo",
Summary = "how long until one wins in gutted bingo-like games",
}
and the second is
@Article{gch:j:generalized-line-bingo,
author = "GCHQ Problems Group",
title = "Generalized Line Bingo (Problem and Solution)",
journal = "American Mathematical Monthly",
year = 1999,
volume = 106,
number = 1,
pages = "72",
}
Groups for Project 2 (note: if people add/drop such
people will go in/out of groups):
Group G:
Peter Andrews,
Garrett Hall,
Chase Hermsen,
Brandon Peterman,
Dennis Wheeler.
Group H:
Daniel Bartkowski,
Stephan Delmer,
Marin Kobin,
Jeffrey Osborn,
Andrew Richardson.
Group R:
Cole Brown,
Francis Ferraro,
Bradley Orego,
Robert Yoon,
Jacob Scheiber.
Group S:
Aaron Gorenstein,
Sara Melnick,
Evan Vandegriff,
Gregory Wilbur,
Andrew Wood.
Here is an n=4 instance where there are 45 tokens without a single bingo. 0111 1101 1110 1011 1110 1001 0111 1101 1011 1000 1101 0111 1101 0111 1011 1110And, in case you don't like that plaintext flattening of the cube, Adam emailed to me this (note: you'll need to hand this file to Matlab to see and manipulate the picture), along with this comment: ``Attached is a Matlab 3D [version of the example that Daniel sent] that you can put on the website as well for everybody to see. The nonexisting bingos can be checked by rotating the figure so that one looks along a direction of possible bingos and checks that there are at most 3 squares.''
Supervisor Versions (always use the most recent, i.e., the last on this list)
Groups for Project 3 (note: if people add/drop such
people will go in/out of groups):
Group G:
Stephan Delmer,
Francis Ferraro,
Aaron Gorenstein,
Chase Hermsen,
Robert Yoon.
Group H:
Sara Melnick,
Brandon Peterman,
Andrew Richardson,
Gregory Wilbur,
Andrew Wood.
Group R:
Peter Andrews,
Cole Brown,
Bradley Orego,
Jeffrey Osborn,
Dennis Wheeler.
Group S:
Daniel Bartkowski,
Garrett Hall,
Marin Kobin,
Jacob Scheiber,
Evan VanDeGriff.
Subject: A new contender for any unofficial Vector tournaments From: Garrett Hall To: cs200 Cc: the other members of Slytherin: marin, jake, daniel, and even Hi Professor Hemaspaandra, I have a new contender for whatever unofficial Vector tournaments inevitably follow the official 13-game one. Although "eigen" is the official submission for the Sylitherin group owing to its faster development, this new agent "Voldemort" performs comparatively well in the trials I've run and is completely different in both design and code. Of course I don't expect this submission will affect anyone's grade, so Voldemort will just be for the honor/glory/bragging rights of the Sylitherin team. It can be made available to whoever is interested. Thanks, Garrett Hall
We indeed won't enter it in the tournament (since all the groups shared the same deadline, and so the official entries of the other groups were ready by the deadline, as was Slytherin's "eigen" program, as Garrett carefully and fairly notes). However, since Garrett says it can be made available to any interested parties, you can find as this zip archive the "Voldemort" agent (and perhaps we'll in class tomorrow here from Garrett or his groupmates a bit more about how Voldemort approaches the game, and of course you all are more than free to download it and run it against your players---to find, for example, how three copies of your group's player do against Voldemort!).
From no-reply@arXiv.org Mon Apr 27 02:08:31 2009 Date: Mon, 27 Apr 2009 02:07:30 -0400 X-Supported-By: U.S. National Science Foundation, Agreement 0132355 (7/01-6/04) Reply-To: cs@arXiv.org To: rabble@arXiv.org (cs daily title/abstract distribution) Subject: cs daily Subj-class mailing 2 1 ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Send any comments regarding submissions directly to submitter. ------------------------------------------------------------------------------ Archives at http://arxiv.org/ To unsubscribe, e-mail To: cs@arXiv.org, Subject: cancel ------------------------------------------------------------------------------ Submissions to: Computational Complexity received from Thu 23 Apr 09 20:00:01 GMT to Fri 24 Apr 09 20:00:02 GMT ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ \\ arXiv:0904.3912 Date: Fri, 24 Apr 2009 18:01:54 GMT (70kb,S) Title: Refutation of Aslam's Proof that NP = P Authors: Frank Ferraro, Garrett Hall, Andrew Wood Categories: cs.CC Comments: 15 pages, 2 figures, a response to Aslam's paper (arXiv:0812.1385v11) and the underlying arguments (arXiv:0812.1385v9) ACM-class: F.2.0; F.2.2 \\ Aslam presents an algorithm he claims will count the number of perfect matchings in any incomplete bipartite graph with an algorithm in the function-computing version of NC, which is itself a subset of FP. Counting perfect matchings is known to be #P-complete; therefore if Aslam's algorithm is correct, then NP=P. However, we show that Aslam's algorithm does not correctly count the number of perfect matchings and offer an incomplete bipartite graph as a concrete counter-example. \\ ( http://arxiv.org/abs/0904.3912 , 70kb) ------------------------------------------------------------------------------ \\ arXiv:0904.3927 Date: Fri, 24 Apr 2009 19:32:10 GMT (6kb) Title: A Critique of "Solving the P/NP Problem Under Intrinsic Uncertainty", arXiv:0811.0463 Authors: Andrew Keenan Richardson, Cole Arthur Brown Categories: cs.CC Comments: 7 pages \\ Although whether P equals NP is an important, open problem in computer science, and although Jaeger's 2008 paper, "Solving the P/NP Problem Under Intrinsic Uncertainty" (arXiv:0811.0463) presents an attempt at tackling the problem by discussing the possibility that all computation is uncertain to some degree, there are a number of logical oversights present in that paper which preclude it from serious consideration toward having resolved P-versus-NP. There are several differences between the model of computation presented in Jaeger's paper and the standard model, as well as several bold assumptions that are not well supported in Jaeger's paper or in the literature. In addition, we find several omissions of rigorous proof that ultimately weaken this paper to a point where it cannot be considered a candidate solution to the P-versus-NP problem. \\ ( http://arxiv.org/abs/0904.3927 , 6kb)