Michael Forbes "Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in Any Order" and Ali Vakilian "Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements"

For Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in Any Order:

Abstract: It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for read-once oblivious branching programs. There are well-known results in this area (due to Nisan, and Impagliazzo-Nisan-Wigderson), but they fail to achieve optimal seed-length. Further, it has been observed that these pseudorandom generators depend strongly on the "order" of the "reads" of the branching program. When this order is allowed to vary, only much weaker results are known.

In this work, we consider an "algebraic" version of this question. That is, we seek to fool read-once algebraic branching programs,regardless of the variable order. By rephrasing and improving the techniques of Agrawal-Saha-Saxena, we are able to construct hitting sets for multilinear polynomials in this unknown-order model that have polylogarithmic "seed-length". This constitutes the first quasipolynomial-time, deterministic, black-box polynomial identity testing (PIT) algorithm for this model.

Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).

For "Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements"

Abstract: We consider degree bounded network design problems with element and vertex connectivity requirements. In the degree bounded Survivable Network Design (SNDP) problem, the input
is an undirected graph G = (V;E) with weights w(e) on the edges and degree bounds b(v) on the vertices, and connectivity requirements r(uv) for each pair uv of vertices.
The goal is to select a minimum-weight subgraph H of G that meets the connectivity requirements and it satises the degree bounds on the vertices: for each pair uv of vertices, H has r(uv) disjoint paths between u and v; additionally, each
vertex v is incident to at most b(v) edges in H. We give the rst (O(1);O(1) b(v)) bicriteria approximation algorithms for the degree-bounded SNDP problem with element connectivity requirements and for several degree-bounded SNDP
problems with vertex connectivity requirements. Our algorithms construct a subgraph H whose weight is at most O(1)times the optimal such that each vertex v is incident to at most O(1) b(v) edges in H. We can also extend our approach
to network design problems in directed graphs with
out-degree constraints to obtain (O(1);O(1) b+(v)) bicriteria approximation

Joint work with Alina Ene