A new post at Computational Complexity asks the following question:
(Problem 1.) You are trying to determine a secret integer x between 1 and n inclusive, using only queries of the form “is x = a (mod b)?” for integers a and b of your choosing. How many queries are required to determine x in the worst case?
And more restrictively,
(Problem 2.) Same as above but you are only allowed to make queries where b is prime.
The comments section seems to reveal at least a partial solution, but these are fun problems, so at least give them a shot before reading the solution there (or here.) If you’d like the solution spoiled anyway, read on! Read more…
Uncategorized
Complexity, CS, Math
Who says computer scientists don’t know how to have fun? As a counterexample, consider a new post over at Gödel’s Lost Letter that was obviously the result of some Wednesday-night festivities and intoxication.
I think, in a sense, we are the accelerators. As we smash ideas together sometimes we discover the further structure of our fundamental particles—our complexity classes.
Duuuuude.
Uncategorized
Complexity, CS, Science!
Virtually everyone with a CS blog (see Scott Aaronson, Luca Trevisan, and the Complexity Blog) has for the past several weeks been going on about Mark Braverman’s recent proof of the Linial-Nisan conjecture. I don’t have too much to add to the discussion, being a neophyte to much of this stuff, but I did attend a talk Braverman gave at the University of Calgary today, in which he outlined his proof (which is remarkably short, for a proof of a conjecture that took nearly 20 years to solve.) Braverman illustrated his arguments with pictures, which really helped me get a handle on his techniques. Read more…
Uncategorized
Complexity, CS