Now showing items 1-11 of 11

    • Algorithmic, game theoretic and learning theoretic aspects of distributed optimization 

      Ehrlich, Steven Jeremy (Georgia Institute of Technology, 2016-08-26)
      Distributed systems are fundamental to today's world. Many modern problems involve multiple agents either competing or coordinating across a network, and even tasks that are not inherently distributed are often divided ...
    • Approximation algorithms for multidimensional bin packing 

      Khan, Arindam (Georgia Institute of Technology, 2015-09-01)
      The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. In the classical bin packing problem, we are given a list of real numbers ...
    • Dual algorithms for the densest subgraph problem 

      Sawlani, Saurabh Sunil Sunil (Georgia Institute of Technology, 2020-05-19)
      Dense subgraph discovery is an important primitive for many real-world graph mining applications. The dissertation tackles the densest subgraph problem via its dual linear programming formulation. Particularly, our ...
    • Efficient high-dimensional sampling and integration 

      Cousins, Benjamin (Georgia Institute of Technology, 2017-05-31)
      Volume computation is an algorithmic version of the fundamental geometric problem to figure out how much space an object occupies. Related problems of sampling and integration have numerous applications to other fields, ...
    • LP and SDP extended formulations: Lower bounds and approximation algorithms 

      Roy, Aurko (Georgia Institute of Technology, 2017-05-24)
      In this thesis we study various aspects of linear and semidefinite programs including their limitations in approximating various combinatorial optimization problems as well as applications of these paradigms in solving ...
    • Markov chains for weighted lattice structures 

      Bhakta, Prateek Jayeshbhai
      Markov chains are an essential tool for sampling from large sets, and are ubiquitous across many scientific fields, including statistical physics, industrial engineering, and computer science. To be a useful tool for ...
    • Modern aspects of unsupervised learning 

      Liang, Yingyu (Georgia Institute of Technology, 2014-06-23)
      Unsupervised learning has become more and more important due to the recent explosion of data. Clustering, a key topic in unsupervised learning, is a well-studied task arising in many applications ranging from computer ...
    • Phase transitions in the complexity of counting 

      Galanis, Andreas (Georgia Institute of Technology, 2014-05-16)
      A recent line of works established a remarkable connection for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function ...
    • Probabilistic techniques for analyzing sampling algorithms and the dynamics of lattice models 

      Fahrbach, Matthew (Georgia Institute of Technology, 2019-11-11)
      Statistical mechanics bridges the fields of physics and probability theory, providing critical insights into both disciplines. Statistical physics models capture key features of macroscopic phenomena and consist of a set ...
    • The complexity of expansion problems 

      Louis, Anand (Georgia Institute of Technology, 2014-06-26)
      Graph-partitioning problems are a central topic of research in the study of algorithms and complexity theory. They are of interest to theoreticians with connections to error correcting codes, sampling algorithms, metric ...
    • The effects of bias on sampling algorithms and combinatorial objects 

      Miracle, Sarah (Georgia Institute of Technology, 2015-04-03)
      Markov chains are algorithms that can provide critical information from exponentially large sets efficiently through random sampling. These algorithms are ubiquitous across numerous scientific and engineering disciplines, ...