Sign In

Communications of the ACM

Blogroll



From Computational Complexity

If you want to help your bad students DO NOT give an easy exam

1) When I was a grad student TAing Formal Lang Theory we had a final ready to give out but noticed that one problem was too hard. So we changed it. But we made...

From Computational Complexity

Other fields of math don't prove barrier results- why do we?

Before FLT was solved did some people prove theorems like: FLT cannot be proven using techniques BLAH. This is important since all current proofs use BLAH. Ihere...

From Computational Complexity

why are regular expressions defined the way they are

BILL: The best way to prove closure properties of regular languages is to first prove  the equiv of DFA's, NDFA's and Reg Expressions. Then, if you want to prove...

From Computational Complexity

Should we learn from the Masters or the Pupils (Sequel)

A while back I had a blog entry Should we learn from the Masters of the Pupils? The Masters may have more insights but he Pupils may have a better view aided by...

From Computational Complexity

The benefits of Recreational Mathematics

Why study Recreational Mathematics? Why do recreational Mathematics? 1)  The line between recreational and serious mathematics is thin. Some of the problems in...

From Computational Complexity

Raymond Smullyan: Logician, Recreational math writer, Philosopher, passed away

Raymond Smullyan was born on May 25 1919 and passed away recently at the age of 97.  He was a logician (PhD from Princeton under Alonzo Church in 1959) who didThe...

From Computational Complexity

The Hardness of Reals Hierarchy

In my last post (here) I defined the following hierarchy (which I am sure is not original- if someone has a source please leave a comment on it) Z_d[x] is theProblems...

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...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Read CACM in a free mobile app!
Access the latest issue, plus archived issues and more
ACM Logo
  • ACM CACM apps available for iPad, iPhone and iPod Touch, and Android platforms
  • ACM Digital Library apps available for iOS, Android, and Windows devices
  • Download an app and sign in to it with your ACM Web Account
Find the app for your mobile device
ACM DL Logo