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
What was the first result in complexity theory?
Let Z_d[x] be the set of polynomials of degree d over the integers. Let ALG_d be the set of roots of polys in Z_d. One can easily show that ALG_1 is a proper...
From Computational Complexity
My Once-Every-Four-Years Presidential Quiz/How Should Quizzes Work in the e-Era?
Every four years I post a PRESIDENTIAL QUIZ which I must update based on new information since we have a new prez and veep. The questions are here:here. I...
From Computational Complexity
My REU program/REU's in general/Flyers? Why do some Transcripts...
I run an REU program (Research Experience for Undergraduates) and I would normally urge you to urge undergrads who would benefit to apply to it and present both...
From Computational Complexity
Guest Post about the first Women in Computational Topology (WinCompTop) Workshop
The first Women in Computational Topology WinCompTop workshop was held in August at the Institute for Mathematics and its Applications (IMA) in Minneapolis, MN....
From Computational Complexity
Predictions for 2017
Lance's Complexity Year in Review, posted the last week of the year (lets hope that P vs NP is not resolved on Dec 31) is a tradition that goes back to 2002. Bill...
From Computational Complexity
The very first Ramseyian Theorem
Many years ago I noticed that in several books on Ramsey Theory mention that Hilbert proved the first Ramseyian theorem. The theorem is the Hilbert Cube...
From Computational Complexity
Guest post by Samir Khuller on Humans, Machines, and the Future of Work (a workshop)
Guest Post from Samir Khuller on Humans, Machines, and the Future of Work (A Workshop) On Dec 5th and 6th I attended, at Rice University, a workshop on Humans...
From Computational Complexity
A students unusual proof might be a better proof
I asked a student to show that between any two rationals is a rational. She did the following: if x < y are rational then take δ << y-x and rational and use...
From Computational Complexity
Guest post by Samir Khuller about Visiting the Simons theory Inst for Computing
Guest post by Samir Khuller on his visit to the Simons Inst. of Computing Visiting the Simons Institute for Theory of Computing A few days back I had the good...
From Computational Complexity
Should I tell HS students that if they do well I'll write them a letter OR do I want them to ...
I teach a 3-week intense course for HS students on cryptography during the summer. Some of the students are very good, interested, and working hard. I also give...
From Computational Complexity
Did you do research when you were an undergrad? Well.. it was a different time.
Dan is a high school student who has worked with me and is now an ugrad at College Park DAN: Bill, did you do research when you were in high school? BILL: No...
From Computational Complexity
And the winner is... Harambe
Tomorow is the Election for Prez of the USA! This post is non-partisan but, in the interest of full disclosure, I state my politics: I will be voting for Hillary...
From Computational Complexity
My chair wants me to post about.. Mohammad Haj wants me to post about.. I want to post about...
Maryland is looking to hire lecturers and my chai Samir wants me to post it on my blog. I think he overestimates the power of the blog, however, here is the link...
From Computational Complexity
Exaggeration is one thing but this is....
This website is about the history of math and lists famous mathematicians. The ones from the 20th century are biased towards logic, but you should go there yourself...
From Computational Complexity
This university does not discriminate based on....
I recently came across the following (I delete the name of the school) and also add my own comments in caps as they relate to UMCP hiring of professors. X-University...
From Computational Complexity
Ideal courses for a comp sci dept/I'm glad we don't do it
I once heard it said: In our data structures course we read Knuth and ignore the proofs In our algorithms course we read Knuth and ignore the code. And indeed...
From Computational Complexity
A Second Order Statement true in (R,+) but not (Q,+)
In my last post I asked Is there a first order statement true in (R,+) but false in (Q,+) Is there a second order statement true in (R,+) but false in (Q,+) ...
From Computational Complexity
Give a second order statement true in (R,+) but false in (Q,+) or show there isn't one
Here is a logic question I will ask today and answer next week. Feel free to leave comments with the answer- you may come up with a different proof than me and...
From Computational Complexity
I have consulted four times. Really!
Those who know me know that I work on stuff that is not readily applied. Or perhaps not applied at all. Certainly my current state of knowledge does seem like it...
From Computational Complexity