A hypergraph is said to be χ-colorable if its vertices can be colored with χ colors so that no hyperedge is monochromatic. 2-colorability is a fundamental property (called Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a 2-colorable k-uniform hypergraph, it is NP-hard to find a 2-coloring miscoloring fewer than a fraction 2^{−k+1} of hyperedges (which is achieved by a random 2-coloring), and the best algorithms to color the hypergraph properly require ≈n^{1−1/k} colors, approaching the trivial bound of n as k increases.

In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a 2-coloring with fewest miscolored edges) and minimization (finding a 2-coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have the following stronger properties than 2-colorability:

(A) Low-discrepancy: If the hypergraph has discrepancy ℓ≪√k, we give an algorithm to color the it with ≈n^O(ℓ^2/k) colors. However, for the maximization version, we prove NP-hardness of finding a 2-coloring miscoloring a smaller than 2^{−O(k)} (resp. k^{−O(k)}) fraction of the hyperedges when ℓ=O(logk) (resp. ℓ=2). Assuming the UGC, we improve the latter hardness factor to 2^{−O(k)} for almost discrepancy-1 hypergraphs.

(B) Rainbow colorability: If the hypergraph has a (k−ℓ)-coloring such that each hyperedge is polychromatic with all these colors, we give a 2-coloring algorithm that miscolors at most k^{−Ω(k)} of the hyperedges when ℓ≪√k, and complement this with a matching UG hardness result showing that when ℓ=√k, it is hard to even beat the 2^{−k+1} bound achieved by a random coloring.

Joint work with Venkatesan Guruswami and Euiwoong Lee.

The publish-subscribe network design problem is defined on a metric with given publisher and subscriber nodes and demands between them. The goal is to build networks (trees) for each publisher and subscriber of minimum total cost where for each demand pair their networks overlap. I will show the natural LP for this problem has an Omega(log log n) integerality gap.

Fifty years of algorithms research has focused on settings in which reads and writes have similar cost. However, several emerging technologies for computer memory have the property that the cost of reading is significantly cheaper than the cost of writing. In this talk, we introduce new models that account for this difference, which includes the RAM model, the PRAM model, the External Memory model, and the Ideal-Cache model. We also briefly mention some lower and upper bounds for various problems under such asymmetric read and write costs (i.e. the Asymmetric RAM model).