Let G_P be the underlying comparability graph of the poset P, i.e. S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G_P)/(\chi(G_P)-1) \le dim(P) \le 2 box(G_P), where \chi(G_P)$ is the chromatic number of G_P and \chi(G_P) \ne 1. It immediately follows that if P is a height-2 poset, then box(G_P) \le dim(P) \le 2 box(G_P), since the underlying comparability graph of a height-2 poset is a bipartite graph.
The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G_c: Note that G_c is a bipartite graph with partite sets A and B which are copies of V(G) such that corresponding to every vertex u of V(G), there are two vertices u_A in A, and u_B in B and (u_A,v_B) is an edge in G_c if and only if either u=v or u is adjacent to v in G. Let P_c be the natural height-2 poset associated with G_c by making A the set of minimal elements and B the set of maximal elements. We show that boxi(G)/2 \le dim(P_c) \le 2 box(G)+4.
In the second part we will survey results regarding the Direct Sum and Direct Product questions in various models of communication complexity. These questions essentially ask if it is possible to compute k simultaneous instances of a function f, more efficiently than using k-times the resource required for a single instance ?
Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to non-product distributions, of the two-way product subdistribution bound of J., Klauck and Nayak, 2008. Our direct product result therefore generalizes to non-product distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck, 2010. We show this by showing that our new complexity measure gives tight lower bound of Omega(n) for the set-disjointness problem on n-bit inputs. In addition we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
Talk based on http://www.eccc.uni-trier.de/report/2011/024/
Joint with Amit Kumar.
All previous attempts at black-box identity tests was via "rank bounds" (introduced by Dvir and Shpilka). These approaches essentially converted the circuit to an "isomorphic" circuit over few variables (as many as the rank). Over the field of rationals, Kayal and Saraf showed that the rank of the circuit is bounded by a function of k alone (where k is the top fan-in), using a deep theorem on geometry of points in R^n. This directly translated to a polynomial time blackbox algorithm for bounded fan-in depth 3 circuits. Saxena and Seshadri subsequently improved the dependence on k, and also showed a rank bound of k^2 log d over finite fields (where d is the degree). However this translated to a quasipolynomial time blackbox algorithm due to the dependence on d. This was unavoidable as there is a rank lower bound of k log d over finite fields (Kayal and Saxena 2007).
In this paper Saxena and Seshadri deviate and preserve a "certificate for non-zeroness" rather than creating an isomorphic circuit. By looking carefully at the Kayal-Saxena test, they extract a "low-rank-ideal" that certifies non-zeroness of the circuit. They then show how this ideal can be preserved by similar transformations, thus yielding the result.