2:41 PM
Both algorithms make sense for undirected graphs as well: we can view K_n as directed graph by doubling each edge. But unlike Bellman-Ford, Dijkstra does not construct a DAG -- he rather solves the recurrence via successive approximation of distances. On NP vs P/poly via monotone circuits: this could interest you.
1 hour later…
3:47 PM
very interesting! close to my own ideas. will dig into it. surprised theres not much word about it so far. how did you hear about it? reminds me of the Deolalikar proof from a few yrs ago which caused a lot of commotion at the time. this overall approach is already immed more conventional/credible....
4:11 PM
you say in your writeup "If the answer is YES, this would show that the Bellman-Ford is optimal in a wide class of DP algorithms." what wide class are you talking about? doesnt seem clear...
it occurs to me that maybe there are prob papers that try to prove how "optimal" bellman-ford is ... have you looked in that direction? if you wrote this up as a proof, what papers would you cite if any?
starting with something simpler: is it true that one can just start with K_n and enumerate all s-t paths in K_n? is there some other simpler way to characterize this set? wondering, what is a rough estimate of the number of these paths?
also it occurs to me that for each K_n "represented" by a DAG, there would probably be a minimal size DAG that represents K_n, true? does it make sense to focus only on the minimal size DAG and not others?
my instinct is to study problems like this empirically esp for problems that are "small" in growth eg polynomial. acc to your writeup one should be able to list out minimal G_n and they only grow in size O(n^3)... how hard would it be to write code that finds those G_n? do you have grad students lying around that can work on this? thats what steven hawking does, wink =)
2 hours later…
6:32 PM
I am trying to reply in a row. He submitted the paper to a journal, so we'll see. (I had no time to check the details, have had only some general comments, as why Razborov fails and he not.)
Bellman-ford DP algorithm is "incremental" (see, e.g. here. If YES, it would be optimal in this class.
What papers to I'd cite: one of them is Kerr 1976 showing that the Floyd-Warschal DP algorithm for the all-pairs shortest paths is optimal if only Min and Plus operations are used.
The number of all simple s-t paths in K_n is easy to give: it is about the sum over all $k\in [n]$ of $n!/(n-k)!$.
Empirical approach may be too boring. Things here may be easier. Say, it is enough to show that paths in DAG representing the paths in $K_n$ with $k$ edges cannot meet too often, for otherwise we could force a path in DAG whose labels do not contain an s-t path.
P.S. To my last comment: Stop all paths in DAG representing the s-t paths of length k after their i-th mark (i<k), and show that there must be about n *distinct" "stopping nodes in DAG. Then the DAG must have about n^2 nodes, and about n^3 edges. Cases k=1,2 are easy. We "only" need to get rid with larger k's.
6:53 PM
- "had had only some general comments, as why Razborov fails and he not".. can you elaborate on that
- do you ever read rj lipton blog? his coverage of looking at the polytope associated with travelling salesman problem reminds me of your directions
7:10 PM
On Juni's paper: it's difficult to elaborate. Let's wait for the paper. Lipton's blog is great. But polytopes for TSP question is much, much harder. Yes, permutations (of various lengths) is a right modell for s-t paths. Empirical: even if we only have O(n^3) edges, there may be exp(n^3) DAGs to consider.
7:22 PM
On Jun's paper again: he also uses a kind of "approximation" (with refined Sunflower Lemma). But Razborov here shows that no argument based on approximating the gates will work for general circuits. This was my biggest trouble.
- looked for links on google to jun's paper but there seem to be none so far. do you know his bkg? the approach is plausible but his style seems "different" .. maybe nonacademic .. has he written any other papers? seems not so far ..
- razborovs impossibility proof of approximation for general circuits. have heard that cited before in obscure places. have you read it?
- it appears you are looking into a sort of DAG-based "compression algorithm" for permutations-of-subsets...
- maybe unf for JF has the same name as famous japanese voice actor...?! surely not the same guy... it might interfere somwhat with him getting his paper taken seriously...
- found his paper "hamming distance between two uniform set systems". says hes in dept math/CS at Indiana State University, Terre Haute, IN. but going to their web site & searching on his last name in directory leads to no result...?
2 hours later…
« first day next day → last day (43 days later) »
Transcript for
Dec6
Dec '127
Dec8
Discussion between vzn and Stasys
Imported from a comment discussion on cstheory.stackexchange.c...