Communications of the ACM
Refine your search:
How the “Frontier” Became the Slogan of Uncontrolled AI
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration …
From Computational Complexity
Fractional Problems: 2.1-colorable, 2.8-SAT
Some graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factionalhere...
From Computational Complexity
How valuable is a Fields Medal?
(Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See here for more info on the Hastad winning it...
From Computational Complexity
The Future of TCS Workshop, celebrating V Vazirani 60th, now online
On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the occasion of his 60th birthday...
From Computational Complexity
Three trick questions in Formal Lang Theory
There are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised...
From Computational Complexity
Need EASY approaches to getting unif random from non-random sources
Teaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a complaint- good to be forced...
From Computational Complexity
The Six Degrees of VDW
A long long time ago a HS student, Justin Kruskal (Clyde's son) was working with me on upper bounds on some Poly VDW numbers (see here for a statement of PVDW)...
From Computational Complexity
Soliciting answers for THIRD survey about P vs NP
I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra) on P vs NP and related topics. Lane has asked me to do a third. I annouced...
From Computational Complexity
The BREAKTHROUGH on Chromatic Number of the Plane (guest post)
(The new SIGACT News chair wnated me to post a letter he send to all SIGACT members on my blog in case you are not in SIGACT. He thinks you should be. I think so...
From Computational Complexity
The Muffin Problem
I've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought...
From Computational Complexity
Its good to be mii
When I taught ugrad Elementary Theory of Computation (Reg, CFL, P, NP, Dec, c.e.) I made 5% of the grade be MEET THE PROF- come to my office, in groups of 3-6...
From Computational Complexity
How the Villarino-Gasarch-Regan paper came about
(This post overlaps a prior one here. The paper I am blogging about was also blogged about by Lipton here. The paper itself is on arxiv here. My slides for a talk...
From Computational Complexity
I tell my class that P is important because... but is that really true?
When teaching P vs NP the questions arises (and if not then I bring it up) what if you have algorithm in P that takes n^{100} time?. Or even n^{5} time which might...
From Computational Complexity
Why is someone emailing me an offer to apply to be chair?
I recently go the following email (I blocked out identifying information of who send it and what college is involved. I doubt I needed to legally but... you never...
From Computational Complexity
COMPUTER PROOF vs computer proof- Quadratic VDW theorem
Quad VDW Theorem: For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d2 are the same color. What is known...
From Computational Complexity
What does it mean for a student to guess an answer?
On my final in Aut Theory I wanted to ask a TRUE/FALSE/UNKNOWN TO SCIENCE question but did not want them to guess. Hence I had +4 for a right answer, -3 for a wrong...
From Computational Complexity
Second of N posts on G4G13. Maybe
(Don't forget to vote for SIGACT posistions:here 9th workshop on Flexible network design, May 22-25 at College Park, here.) My first poston G4G13 is arguably ...
From Computational Complexity
Gahering for Gardner 13 - the first or third of many posts
I attended G4G13 (Gathering for Gardner- meeting 13). Martin Gardner was the Scientific American Mathematical Recreations columnist from 1956 until 1981. He had...
From Computational Complexity
The 8 digit number I asked for
(On June 29th, co-located with STOC, there will be a workshop to celebrate Vijay Vazarani's 60th birthday. See here. As computer scientists shouldn't we use 64...
From Computational Complexity
Find an 8-digits number such that ....
(June 29th, co-located with STOC, will be a workshop to celebrate Vijay Vazarani's 60th birthday. As computer scientists shouldn't we use 64 as the milestone?here...
From Computational Complexity