Sign In

Communications of the ACM

Blogroll



From Computational Complexity

A New ACO Center (guest post by Vijay Vazirani)

Guest Post by Vijay Vazirani                                                           A New ACO Center! Last week, I helped launch an ACO Center (Algorithms,...

From Computational Complexity

John Sidles, Mike Roman, Matt Howell, please email me/hard to get emails of people

John Sidles, Mike Roman, Matt Howell : please email me. at gasarch@cs.umd.edu (my usual email) I need to ask you about some comments you left on the blog a while...

From Computational Complexity

Google added years to my life

If you google gasarch you used to  get the following:   here Please go there and notice how old they say I am. Okay, you are back. You may have noticed that...

From Computational Complexity

What is a Physicist? A Mathematician? A Computer Scientist?

 Scott Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!). In his post (here) about it he makes a passing comment: I'm of course not...

From Computational Complexity

The Tenure system is broken but not in the way that you think (Anon Guest Post)

This is an ANONYMOUSE Guest Post. Even I don't know who it is! They emailed me asking if they could post on this topic, I said I would need to see the post, and...

From Computational Complexity

The Rule of Threes/Astology

On Aug 16, 2018 Aretha Franklin died. A famous singer. On Aug 18 2018 Kofi Anan died. A famous politician. On Aug 25, 2018 John McCain died. A famous politician...

From Computational Complexity

Is Trivium (the Stream Cipher) used?

This Fall I am teaching the senior course in Crypto at UMCP. Its a nice change of pace for me since REAL people REALLY use this stuff! Contrast to last Spring when...

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...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account