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
Tucker Bane is a friend of mine who has an AWESOME video game availablethat is called BYTE LYNX.I am curious- Can I be an INFLUENCER!Lets find out!At the link below...gasarch From Computational Complexity | October 18, 2022 at 02:02 AM
All time bounds are asymptotic and really O-of.Recall that Strassen found a clever way to multiple two 2x2 matrices with 7 mults (and lots of adds) leading tohere...gasarch From Computational Complexity | October 10, 2022 at 12:03 AM
One of the proofreaders for Computational Intractability: A Guide to Algorithmic Lower Bounds(available here)made the following objection, which raises some questions...gasarch From Computational Complexity | October 4, 2022 at 10:05 AM
RECALL:A max-problem f has a A P Time App Scheme (PTAS) if there is an algorithm ALG such that ALG(\epsilon) \ge (1-\epsilon)f(x).A min-problem f has a A P Time...gasarch From Computational Complexity | September 26, 2022 at 10:02 PM
We have posted a revised version of Computational Intractability: A Guide to Algorithmic Lower Boundsby Demaine-Gasarch-HajiaghayiThe book is here.(For the original...gasarch From Computational Complexity | September 21, 2022 at 04:48 PM
Alice and Bob have the following conversation.===============================ALICE: In your book you define INT PROG as, given a matrix A and vectors b,c,find the...gasarch From Computational Complexity | September 19, 2022 at 03:02 PM
As I am sure you know, Queen Elizabeth II passed away at the age of 96 recently. I am not a royal-watcher, but I am a royal-watcher-watcher. That is, the question...gasarch From Computational Complexity | September 15, 2022 at 04:41 PM
(This post is written by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi)In 1979 Garey and Johnson published the classic Computers and Intractability...gasarch From Computational Complexity | August 24, 2022 at 11:09 PM
This is a non-partisan post. In the interest of disclosure I will divulge that I do not think private citizens should have top secret government documents in their...gasarch From Computational Complexity | August 15, 2022 at 08:13 AM
Dan Spielman asked me to blog about the Held Prize. I first present what he send me, and then have some thoughts.FROM DAN: ------------------------------------...gasarch From Computational Complexity | August 7, 2022 at 08:21 AM
Juris Hartmanis, one of the founders of Complexity Theory, passed away on July 29 at the age of 94. The Gödel's Last Letter blog has an obit posted here. When...gasarch From Computational Complexity | July 30, 2022 at 12:09 PM
I was recently emailed this link:
100 Best Number Theory books of all Time
That sounds like a good list to have! But then I looked at it. The issue IS NOT that...gasarch From Computational Complexity | July 24, 2022 at 06:46 PM
In my last post I wrote:---------------------------Consider the recurrencea_1=1for all n\ge 2, a_n = a_{n-1} + a_{n/2}.For which M does this recurrence have infinitely...gasarch From Computational Complexity | July 20, 2022 at 10:30 PM
In this post n/2 means floor{n/2}Consider the recurrencea_1=1for all n\ge 2, a_n = a_{n-1} + a_{n/2}.For which M does this recurrence have infinitely many n such...gasarch From Computational Complexity | July 18, 2022 at 10:52 PM
A while back I reviewed A Map that Reflects the Territory which is a collection of essays posted on the lesswrong forum. My review is here. I posted it to both...gasarch From Computational Complexity | July 11, 2022 at 09:22 PM
BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of different 3-colorings it has.) LANCE: Surely you know that for all naturalnatural...gasarch From Computational Complexity | June 26, 2022 at 03:00 PM
I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However...gasarch From Computational Complexity | June 19, 2022 at 03:08 PM
A lattice L in R^n is a discrete subgroup of R^n. Let p IN [1,infinty)The p-norm of a vector x=(x_1,...,x_n) IN R^n is here...gasarch From Computational Complexity | June 12, 2022 at 02:34 PM
A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's...gasarch From Computational Complexity | June 4, 2022 at 01:03 PM
1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans...gasarch From Computational Complexity | May 30, 2022 at 01:25 AM