Galactic Sorting Networks
An improved sorting network to appear at STOC 2014
|
|
Teaching page source |
Michael Goodrich is a Chancellor’s Professor at the University of California at Irvine, and recently served a year as Chair of the UCI Computer Science Department. He has designed algorithms that cover all of the area spanned by axes of cleverness and high performance. This includes attention to algorithms that we have called (clever but) galactic for having enormous constant factors and/or high exponents that forestall practical implementation. An example is his paper last year with his colleague Pawel Pszona, “Cole’s Parametric Search Technique Made Practical,” which greatly tunes up an algorithm-improvement technique of Richard Cole. Now he has a new paper taking a notorious behemoth head-on.
Today Ken and I wish to talk about Michael’s recent work improving on the size of the famous AKS sorting network. Read more…
In Praise Of P=NP Proofs
Why they can be important
|
|
Advertising source |
Joe Bloggs is not a computer scientist, at least not one that we know. As noted by Wikipedia, Joe Bloggs is a “placeholder name” like “John Doe” or “Jane Roe” in the US, or “Ashok Kumar” in India. Sometimes real people have or acquire the placeholder names: Ashok Kumar (born Kumudlal Ganguly) was a famous actor in India, whose acting brothers also took the surname “Kumar,” and the “Roe” in Roe v. Wade is Norma McCorvey. We especially like the fact that “Joe Bloggs” came about long before there were blogs. A public restraining order is indeed called an “Ashok Kumar order” in India the way it is called a “John Doe order” in the US.
Today Ken and I consider whether there should be a “John Doe order” against submitting claimed proofs of 
Read more…
The More Variables, the Better?
Ideas from algebraic geometry and arithmetic complexity
Hyman Bass is a professor of both mathematics and mathematics education at the University of Michigan, after a long and storied career at Columbia University. He was one of the first generation of mathematicians to investigate K-theory, and gave what is now the recognized definition of the first generation of K-groups, that is 
Today Ken and I wish to discuss an idea used in a paper on the Jacobian Conjecture by Bass with Edwin Connell and David Wright.
Read more…
Multiple-Credit Tests
Can chess statistics help design multiple-choice exams?
|
|
UT Dallas source |
Bruce Pandolfini is one of very few living people who have been played by an Oscar-winning actor. He was the real-life chess teacher of junior chess player Joshua Waitzkin, who went on to become the world champion—in T’ai Chi. Their story is told in the movie “Searching For Bobby Fischer” with Sir Ben Kingsley, which is still iconic after 20-plus years. Pandolfini is still doing what he loves as an active chess teacher in New York City. For much of this time he has also written a popular feature called “Solitaire Chess” for Chess Life magazine, which is published by the United States Chess Federation.
Today Dick and I wish to compare styles of multiple-choice exams, with reference to “Solitaire Chess,” and have some fun as well.
Read more…
Counting Is Sometimes Easy
Cases where we can count objects in polynomial time
|
|
New Interim Dean source—our congrats |
Mike Sipser is one of the top theorists, especially in complexity theory, and has been Head of the Mathematics Department at MIT since 2004. He is long known for some very clever proofs and his famous survey paper on the status of
Today Ken and I wish to talk about a topic that is covered in his book, finite state automata, in relation to counting.
Read more…
Wait Wait… Don’t Fool Me!
It’s that time of year again
|
|
Altered from NPR source. |
Faadosly Polir is back in contact with us. We have encountered him before, but this time he has company. He has teamed up with two well-known radio personalities to launch a quiz show about mathematics.
Today Ken and I wish to talk about material for the show that Faadosly has sent us.
Read more…
A Matchless Result
A famous algorithm, a new paper, a full correctness proof
Vijay Vazirani is one of the world experts on algorithmic theory, and is especially known for his masterful book on approximation algorithms. Among many results in computational complexity, two have been Wikified: his theorem with Les Valiant on unique SAT, and the subsequent generalized Isolation Lemma with Ketan Mulmuley and his brother Umesh Vazirani. Lately his focus has been more on computational aspects of auctions, economic systems, and game theory.
Today Ken and I wish to discuss a recent paper by Vijay on matching.
Read more…
Rabin Meets Lagrange
On Rabin’s recent talks at Tech
Jeffrey Shallit is a computational number theorist, with many wonderful results. He is also well known for his work as an advocate for civil liberties on the Internet, and also against intelligent design (ID). Indeed he was at one point slated to testify in the 2005 Dover case until a stand-down by the ID side accomplished his purpose. Ken once used his survey with Wesley Elsberry in a graduate seminar on cellular automata and various forms of complexity, not to say anything about ID, but just as a source of well-written definitions and relevant examples.
Today I would like to talk about on Michael Rabin’s talks at Tech this week and their connection to Jeff.
Read more…
The Power Of ACC
Euler’s back-door pass to Gauss sinks a bucket
ACC stands for the Atlantic Coast Conference, which is an athletic organization that contains Georgia Tech and fourteen other colleges. In basketball, the top several teams in the ACC qualified for the NCAA championship tournament, which started today. We call the NCAA tournament “March Madness” because the opening rounds have games being shown on national TV seemingly every hour of every day, and often some spectacular upsets happen. Indeed Harvard has just beaten a favored University of Cincinnati team.
Today I want talk about another ACC: our own complexity class. Read more…
Happy St. Patrick’s Day 2014
A shocking story from our friendly Leprechaun
Neil L. is not a computer scientist—he is a Leprechaun. He has visited me every year since I started writing GLL, always visiting on St. Patrick’s day.
Today I want to report on what happened this year.
Read more…
