From Schneier on Security
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration
…
B. Schneier| February 29, 2024
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...GASARCH From Computational Complexity | July 25, 2018 at 09:16 AM
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)...GASARCH From Computational Complexity | July 12, 2018 at 01:33 AM
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...GASARCH From Computational Complexity | July 9, 2018 at 04:05 PM
(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...GASARCH From Computational Complexity | July 2, 2018 at 05:28 PM
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...GASARCH From Computational Complexity | June 22, 2018 at 01:31 PM
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...GASARCH From Computational Complexity | June 17, 2018 at 10:31 PM
(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...GASARCH From Computational Complexity | June 11, 2018 at 12:45 AM
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...GASARCH From Computational Complexity | June 6, 2018 at 07:40 PM
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...GASARCH From Computational Complexity | May 30, 2018 at 12:22 AM
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...GASARCH From Computational Complexity | May 20, 2018 at 10:44 PM
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...GASARCH From Computational Complexity | May 14, 2018 at 11:47 PM
(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 ...GASARCH From Computational Complexity | May 9, 2018 at 08:25 AM
I attended G4G13 (Gathering for Gardner- meeting 13). Martin Gardner was the Scientific American Mathematical Recreations columnist from 1956 until 1981. He had...GASARCH From Computational Complexity | April 30, 2018 at 09:03 AM
(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...GASARCH From Computational Complexity | April 26, 2018 at 10:11 AM
(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...GASARCH From Computational Complexity | April 23, 2018 at 11:56 AM
(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...GASARCH From Computational Complexity | April 16, 2018 at 07:03 PM
(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...GASARCH From Computational Complexity | April 9, 2018 at 01:26 AM
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...GASARCH From Computational Complexity | April 5, 2018 at 10:49 AM
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:
...GASARCH From Computational Complexity | April 3, 2018 at 02:00 PM
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...GASARCH From Computational Complexity | March 26, 2018 at 10:04 AM