Sign In

Communications of the ACM

Blogroll



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

Is DTIME(n) closed under concat? star? of course not but...

(STOC 2018 will offer child care for the first time. I was emailed the following and asked to pass it on: We are pleased to announce that we will provide pooled...

From Computational Complexity

Whan a deep theorem of your Uncles becomes standard should you be sad?

(An exposition of Nash-Williams's proof of  the Kruskal Tree Theorem is here) Andrew Vazsonyi (the mathematician, see here, not the folklorist, see here for that...

From Computational Complexity

Challenge about NFA for {a^y : y\ne 1000} answered.

Recall that in a prior post I asked Is there an NFA for  { ay : y ≠ 1000 } with substantially less than 1000 states. I will now show that any NFA for this set...

From Computational Complexity

Challenge: Is there a small NFA for { a^i : i\ne 1000} ?

Consider the language {L =  ai   : i ≠ 1000 } There is a DFA for L of size 1002 and one can prove that there is no smaller DFA. What about an NFA?  Either: ...

From Computational Complexity

Why do we give citations? How should we give citations?

Why do we cite past work? There are many reasons and they lead to advice on how we should cite past work Give credit where credit it due. Some people over cite...

From Computational Complexity

Wanted: An Easy Proof of a Weak Theorem in NT so that I can get another VDW--> Primes infinite proof to be really easy.

(All math in this article is here) A while back I posted about a proof that Van Der Waerden's theorem implies the number of primes is infinite (see the post...

From Computational Complexity

When the Wrong People raise the issue

On my discrete math final in Spring 2017 I had a question: Prove that sqrt(2/3) is irrational. A student emailed me the folloing (I paraphrase and am prob not...

From Computational Complexity

When students are wrong but have a valid point, encourage them

I often have the class VOTE on a statement (the choices are usually TRUE/FALSE/UNKNOWN TO SCIENCE/Stewart-Colbert-2020) I ask the students who voted incorrectly...

From Computational Complexity

The web bad/People using it bad.

I was going to write a post about how hard it was to find what grades mean at different schools (e.g., at UMCP W (for withdraw) means the student dropped the course...

From Computational Complexity

A ``new'' ``application'' of Ramsey Theory/A Truly ``bad'' math song

Ian Parberry once told me (though I doubt he originated it- The first link I found says it was Mark Twain) to a man with a hammer, everything looks like a nail...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account