From a student today in office hours before today’s midterm: “How many times will the word automata appear in the test, including its use in acronyms like DFA, NFA, GNFA, and WTFA?”
BQP, NP, and All That
The mothership, aka Seed magazine, has a crib sheet for quantum computing. Its not half bad, considering how bad things like this can go. And of course this is probably due in part to the fact that they list the Optimizer as a consultant. But the real question is whether that little shade of black outside of NP is an illustrators trick or the result of a complexity theorist being the person they asked to vet the cheat sheet?
Inspiring Talks: Drew Endy
Good talks are rare gems. Good talks about interesting topics even rarer. Good talks that make you want to change fields and design E. Coli which smell like bananas are the best. I saw a good one earlier this week, and its now online: Learning to Program DNA by Drew Endy. If you get a chance, check out the picture of Drew going off a waterfall in a kayake on the Lower McCloud river. That’s very close to where I grew up (and don’t you city folk come up there and ruin that beautiful neck of the woods. Stay way slicker!)
CSE 322 Week 2: Nondeterminism Rocks
Last week, in the class I’m teaching, we talked about the basics of deterministic finite automata. In week two we moved on to more interesting and slightly less basic material. In particular we introduced the notion of a nondeterministic finite automata and, by the end of the week, had showed that the class of languages accepted by deterministic finite automata is exactly the same class of languages accepted by nondeterministic finite automata.
Continue reading “CSE 322 Week 2: Nondeterminism Rocks”
Der Took Our Science N Engineering Jerbs!
Whatever you do, Mr. and Mrs. Joe and Mary America, make sure to tell everyone you know not to go into science and engineering! You see those who major in science and engineering are certain to not get jobs, because, as many commenters love to point out, all those jobs are being exported overseas! But wait, what is this:
The overall unemployment rate of scientists and engineers in the United States dropped from 3.2% in 2003 to 2.5% in 2006…according to data from the National Science Foundation (NSF) Scientists and Engineers Statistical Data System (SESTAT). This is the lowest unemployment rate measured by SESTAT since the early 1990s. It continues a trend of lower unemployment rates for scientists and engineers compared with unemployment rates in the rest of the U.S. economy.
Who knew? A degree in science and engineering actually appears to help your employment chances 🙂
AP Computer Science AB Cut
The very first AP class I took in high school was the Computer Science AB test. Today, I learn from the Washington Post, that the Computer Science AB test is on the chopping block (along with Italian, Latin literature, and French literature.)
Continue reading “AP Computer Science AB Cut”
The World Market is Five Quantum Computers
From the bits blog at the New York Times, a list of technology famous quotes which may or may not have been said. Two of which I believe I’ve used before (doh!):
“640K ought to be enough for anybody.” This quotation is attributed to Bill Gates, but Mr. Shapiro suspects that it is apocryphal, and is seeking the person who either said it or first attributed it to Mr. Gates.
…
“I think there is a world market for about five computers.” This is a attributed to Thomas J. Watson, Jr., but Mr. Shapiro suspects it of being apocryphal and is seeking the person who either said it or first attributed it to Mr. Watson.
ACM Transactions on Computation Theory
As noted by Lance, the new journal ACM Transactions on Computation Theory is now accepting papers. Note for quantum computing theorists:
ACM Transactions on Computation Theory will cover theoretical computer science complementing the scope of the ACM Transactions on Algorithms and the ACM Transactions on Computational Logic including, but not limited to, computational complexity, foundations of cryptography, randomness in computing, coding theory, models of computation including parallel, distributed and quantum and other emerging models, computational learning theory, theoretical computer science aspects of areas such as databases, information retrieval, economic models and networks.
So next time you write a paper which involves QMA, the Hidden Subgroup, etc. etc. make sure to give ToCT a look!
Bristol Summer School on Probabilistic Techniques in Computer Science
An interesting summer school for computer scientists interested in probabilistic techniques to be held in Bristol, UK (you know the school that had a chalkboard with the statement that quantum computers could efficiently solve NP-complete problems 🙂 ) Deadline fast approaching. Details below.
Continue reading “Bristol Summer School on Probabilistic Techniques in Computer Science”
Because Nature Isn't Classical
Via the Computational Complexity (welcome back Lance), the list of accepted papers for CCC 2008 has been posted. Woot, that’s a lot of quantum inspired papers. By my count 7 of 33. Quoteth Feynman
…and I’m not happy with all the analyses that go with just the classical theory, because nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical…