Poster Session and Reception

Wednesday, March 18, 2015 - 5:00pm - 6:30pm
  • Approximation Algorithms for Vector Bin Packing
    Arindam Khan (Georgia Institute of Technology)
    he d dimensional vector bin packing problem is a classical multidimensional generalization of bin packing problem
    where we are given a set of d-dimensional vectors with nonnegative entries and the goal is to pack these into a minimum number of bins so that for every bin the sum of packed vectors does not exceed the vectors of the bin in each dimension. The problem has numerous application in loading, scheduling, layout design. It has recently received renewed attention in connection with research on virtual machine placement in cloud computing.

    We show a ln(d)+ 0.807 approximation algorithm for d-dimensional vector packing.
    We also show a 1+ ln(3/2) approximation algorithm for 2-dimensional vector packing.
  • Random Intersection Graphs and their Applications in Security, Wireless Communication, and Social Networks
    Jun Zhao (Carnegie-Mellon University)
    Random intersection graphs have received much interest and been used in diverse applications. They are naturally induced in modeling secure sensor networks under random key predistribution schemes, as well as in modeling the topologies of social networks including common-interest networks, collaboration networks, and actor networks. Simply put, a random intersection graph is constructed by assigning each node a set of items in some random manner and then putting an edge between any two nodes that share a certain number of items. Broadly speaking, our work is about analyzing random intersection graphs, and models generated by composing it with other random graph models including random geometric graphs and Erdős–Rényi graphs. These compositional models are introduced to capture the characteristics of various complex natural or man-made networks more accurately than the existing models in the literature. For random intersection graphs and their compositions with other random graphs, we study properties such as (k-)connectivity, (k-)robustness, and containment of perfect matchings and Hamilton cycles. Our results are typically given in the form of asymptotically exact probabilities or zero-one laws specifying critical scalings, and provide key insights into the design and analysis of various real-world networks.
  • Reconstruction and Glauber Dynamics of Colorings on Trees
    Yumeng Zhang (University of California, Berkeley)
    The mixing time of the Glauber dynamics for spin systems on trees is closely related to reconstruction problem. Martinelli, Sinclair and Weitz established this correspondence for a class of spin systems with soft constraints bounding the log-Sobolev constant by a comparison with the block dynamics. However, when there are hard constraints, the block dynamics may be reducible.
    We introduce a variant of the block dynamics proving that the mixing time of the Glauber dynamics for colorings on the regular tree is O(nlog n) in the entire non-reconstruction regime. Our proof also applies for essentially any spin system that has non-reconstruction provided that on average the root is not locally frozen in a large neighborhood. This is joint work with Allan Sly.
  • Spectral Thresholds in the Bipartite Stochastic Block Model
    Laura Florescu (New York University)
    We consider a bipartite stochastic block model on vertex sets V_1 and V_2 of size n and n^k respectively, with planted partitions in each. An algorithm to recover the partition of V_1 was used by Feldman, Perkins, and Vempala to solve instances of planted random k-SAT and planted hypergraph partitioning. The algorithm required O(n^{(k+1)/2}) edges to recover the partition. It was left as an open question whether the straightforward spectral approach of computing the top singular vector of the centered adjacency matrix would suffice at the same edge density.

    We show the answer is no: the straightforward spectral approach requires Omega(n^{(2k+1)/3}) edges. Nevertheless, we give two modifications of the adjacency matrix that lead to simple spectral algorithms that match the previous bound of O(n^{(k+1)/2}).

    Finally, we locate a sharp threshold for detection of the partition, in the sense of the results of Mossel, Neeman, Sly and Massoulie for the stochastic block model. This gives the best known bounds for planted k-SAT and hypergraph partitioning as well as showing a barrier to further improvement via the reduction to the bipartite block model. Joint work with Will Perkins.
  • Catalan Shuffles
    Emma Cohen (Georgia Institute of Technology)
    Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence, and derive estimates on the mixing time of the corresponding Markov chains. While our main result is in deriving an $O(n^2 \log n)$ bound on the mixing time in $L_2$ (and hence total variation) distance for the random transposition chain on Dyck paths, we raise several open problems, including the optimality of the above bound. Joint work with Prasad Tetali and Damir Yeliussizov.
  • Cool with a Gaussian: A Cubic Volume Algorithm
    Ben Cousins (Georgia Institute of Technology)
    Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes and exponential lower bounds for deterministic algorithms in the oracle model). We present a new algorithm, whose complexity grows as n^3 in the oracle model for any well-rounded convex body. The two main new components of this algorithm are more efficient Gaussian sampling and an accelerated cooling schedule. It improves upon the previous best algorithm of Lovász-Vempala from 2003 by a factor of n, and bypasses the famous KLS hyperplane conjecture, which appeared essential to achieving such complexity. We will also demonstrate an implementation based upon our algorithm in MATLAB.
  • Clustering and Mixing Times for Segregation Models on Z^2
    Prateek Bhakta (Georgia Institute of Technology)
    The Schelling segregation model attempts to explain possible causes of racial segregation in cities. Schelling considered residents of two types, where everyone refers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move, called the General Influence Model. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated (i.e., there will not be clustering) if the racial bias is sufficiently low. Next we show complementary results for two broad classes of influence functions: Increasing Bias Functions (IBF), where an individual's likelihood of moving increases each time someone of the same color leaves (this does not include Schelling's threshold models), and Threshold Bias Functions (TBF) with the threshold exceeding one half, reminiscent of the model Schelling originally proposed. For both classes (IBF and TBF), we show that when the bias is sufficiently high, the dynamics take exponential time to mix and we will have segregation and a large ghetto will form.