Posts

Post has attachment

Ryan Williams commented on a post on Blogger.

",I don't think it's even useful to ask the most general form of "what does a neural net DO" questions. Neural nets are very very general"

But if we put bounds on the number of neuronal units we are allowed to have, e.g. polynomial bounds, then it becomes a useful and completely wide open question again, and it's obviously relevant to the enterprise of deep learning. If they are extremely expressive and TC0 = P then the success of deep learning would suggest that crypto as we know it is doomed. If TC0 is much weaker than P, then the success of deep learning in practice suggests that the "nature" case is often so considerably structured computationally that there is likely to be a powerful (and to date, undetermined) alternative to worst case analysis for use in many practical settings.

Either scenario is worth exploring.

But if we put bounds on the number of neuronal units we are allowed to have, e.g. polynomial bounds, then it becomes a useful and completely wide open question again, and it's obviously relevant to the enterprise of deep learning. If they are extremely expressive and TC0 = P then the success of deep learning would suggest that crypto as we know it is doomed. If TC0 is much weaker than P, then the success of deep learning in practice suggests that the "nature" case is often so considerably structured computationally that there is likely to be a powerful (and to date, undetermined) alternative to worst case analysis for use in many practical settings.

Either scenario is worth exploring.

Post has attachment

Public

Ryan Williams commented on a post on Blogger.

Another point for Piotr's side: their hardness result for Edit Distance does not require the full strength of SETH, but rather can also be based on the much more plausible conjecture that the Orthogonal Vector Pair problem (finding an orthogonal pair of vectors in a collection of Boolean vectors) requires essentially quadratic time in the number of vectors. Since then, the hardness of Edit Distance can be concluded from other plausible SAT assumptions (see http://arxiv.org/abs/1511.06022).

Point is, this work has led to connections deeper than simply drawing a bunch of conclusions from one (possibly flimsy) algorithmic hypothesis. It is an instance of a more general phenomenon: connections between seemingly disparate problems, where one can begin to delinate and measure what necessary work must be performed in order to solve Edit Distance.

Point is, this work has led to connections deeper than simply drawing a bunch of conclusions from one (possibly flimsy) algorithmic hypothesis. It is an instance of a more general phenomenon: connections between seemingly disparate problems, where one can begin to delinate and measure what necessary work must be performed in order to solve Edit Distance.

Post has shared content

Join us for the next TCS+ talk! The talk will be given by Ryan Williams, next Wednesday, March 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC; notice that the US is already using daylight savings time).

Please leave a comment below if you plan to join as a group. We will invite you into the hangout 15 minutes ahead of time so that we can make sure everything is working properly. Priority will be given to larger groups.

We have a group limit of 12 spots, which is enough in most cases. So, don't be shy in requesting a seat!

Speaker: Ryan Williams

Affiliation: Stanford

Title: Faster all-pairs shortest paths via circuit complexity

Abstract: The good old all-pairs shortest path problem in dense n-node directed graphs with arbitrary edge weights (APSP) has been known for 50 years (by Floyd and Warshall) to be solvable in O(n^3) time on the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost). Faster algorithms

(starting with Fredman in 1975) take n^3/(log^c n) time for various c <= 2. It's a longstanding open problem if APSP can be solved in n^{3-eps} time for some eps > 0. A first step would be to determine if even an n^3/(log^c n) time algorithm is possible, for

I will outline a new method for computing the min-plus product (a.k.a., tropical product) of two n by n matrices, yielding a faster algorithm for APSP. On the real RAM, the algorithm runs in time O(n^3/2^{(log n)^{delta}}) for any delta > 1/2. The algorithm applies tools from low-level circuit complexity.

Please leave a comment below if you plan to join as a group. We will invite you into the hangout 15 minutes ahead of time so that we can make sure everything is working properly. Priority will be given to larger groups.

We have a group limit of 12 spots, which is enough in most cases. So, don't be shy in requesting a seat!

Speaker: Ryan Williams

Affiliation: Stanford

Title: Faster all-pairs shortest paths via circuit complexity

Abstract: The good old all-pairs shortest path problem in dense n-node directed graphs with arbitrary edge weights (APSP) has been known for 50 years (by Floyd and Warshall) to be solvable in O(n^3) time on the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost). Faster algorithms

(starting with Fredman in 1975) take n^3/(log^c n) time for various c <= 2. It's a longstanding open problem if APSP can be solved in n^{3-eps} time for some eps > 0. A first step would be to determine if even an n^3/(log^c n) time algorithm is possible, for

**every**c.I will outline a new method for computing the min-plus product (a.k.a., tropical product) of two n by n matrices, yielding a faster algorithm for APSP. On the real RAM, the algorithm runs in time O(n^3/2^{(log n)^{delta}}) for any delta > 1/2. The algorithm applies tools from low-level circuit complexity.

Public

Is Google Calendar down or just me? For at least a week, every event I try to add or modify is met with "Oops, we couldn't load your events, please try again in a few minutes"

Post has shared content

Public

This is a surprisingly excellent point:

"Academic material is not meant to be read.

It is meant to be ransacked and pillaged for essential content."

"Academic material is not meant to be read.

It is meant to be ransacked and pillaged for essential content."

Post has attachment

In Prague for a few days. I haven't been in Prague since I was an undergrad participating in the NSF DIMACS/DIMATIA REU program. Giving their 85th Mathematical Colloquium and signing Jarik Nesetril's famous book are the primary highlights so far.

Post has shared content

Post has attachment

Celebrating Erdős by watching this documentary on him:

Paul Erdos - N is a number (Mathematics Asperger)-1.avi

It's interesting, I've met many of the younger mathematicians in this documentary -- of course, when I met them, they were a bit older :) Seeing the young them with the old Erdős is really neat.

Paul Erdos - N is a number (Mathematics Asperger)-1.avi

It's interesting, I've met many of the younger mathematicians in this documentary -- of course, when I met them, they were a bit older :) Seeing the young them with the old Erdős is really neat.

Post has attachment

This is fantastic... I'm teaching Cook's theorem this afternoon!

(thanks to +Kaveh Ghasemloo)

(thanks to +Kaveh Ghasemloo)

Post has shared content

A summer at IBM can do you good.

Summer internships with the theory group at IBM Almaden Research: please see our webpage, https://ibm.biz/BdxSYR

Wait while more posts are being loaded