Refine your search:

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...