I might read this post a little late but it sounds pretty interesting. I checked your paper on eccc, I think on page 10 there is a small typo, positive should be changed to nonnegative at line -8. It is also a bit strange to me that you end by defining two problems…

Anyhow, about the open problem related to the shortest balanced st-path, I guess that it is not possible to go above n^2. I will put here my rough idea, maybe you already thought of it and know that it does not work.

Claim 1. If for all i a_i<n and gcd(a_i's)=1, then there are lambda_i such that sum lambda_i a_i =1 and sum |lambdai_i||a_i| is at most n^2.

These a_i are the unbalancedness numbers of the (simple) cycles that are in the same component as s and t.

Claim 2. If d=gcd(a_i) and there is a balanced st path, then d divides the length of every st path.

I guess you see how the proof would follow from here – take a simple st path, take a suitable collection of lambda_i's given by claim 1, connect all these cycles to the path by going there and back for them.

@domotorp : We recently used a similar technique to prove that both balanced paths and positive balanced paths can only be of polynomial length. I will soon make these results public.

Is there a simple reason why you restrict paths to be of length at most n? Naively, it seems a very artificial cutoff, since you are not considering simple paths and the paths can only have polynomial length anyway.

The restriction on path lengths can be removed since the path lengths are polynomial. However, for the purpose of proving space bounds, we may assume that the length of the path is at most n.

Also, we recently proved that SGSLOGCFL is in L. I will blog about it soon.

why not at cstheory ?

I will ask on cstheory sometime later.

I might read this post a little late but it sounds pretty interesting. I checked your paper on eccc, I think on page 10 there is a small typo, positive should be changed to nonnegative at line -8. It is also a bit strange to me that you end by defining two problems…

Anyhow, about the open problem related to the shortest balanced st-path, I guess that it is not possible to go above n^2. I will put here my rough idea, maybe you already thought of it and know that it does not work.

Claim 1. If for all i a_i<n and gcd(a_i's)=1, then there are lambda_i such that sum lambda_i a_i =1 and sum |lambdai_i||a_i| is at most n^2.

These a_i are the unbalancedness numbers of the (simple) cycles that are in the same component as s and t.

Claim 2. If d=gcd(a_i) and there is a balanced st path, then d divides the length of every st path.

I guess you see how the proof would follow from here – take a simple st path, take a suitable collection of lambda_i's given by claim 1, connect all these cycles to the path by going there and back for them.

@domotorp : We recently used a similar technique to prove that both balanced paths and positive balanced paths can only be of polynomial length. I will soon make these results public.

Whether SGSLOGCFL is in Logspace is still open.

Pingback: Graph Isomorphism of Minor-free Graphs « My Brain is Open

Is there a simple reason why you restrict paths to be of length at most n? Naively, it seems a very artificial cutoff, since you are not considering simple paths and the paths can only have polynomial length anyway.

The restriction on path lengths can be removed since the path lengths are polynomial. However, for the purpose of proving space bounds, we may assume that the length of the path is at most n.

Also, we recently proved that SGSLOGCFL is in L. I will blog about it soon.