Abstracts for Maryland Theory Day 2012

1. 9-10: Distinguished Invited Speaker: Prof. Julia Chuzhoy, Toyota Technological Institute:
   • Title: Approximation algorithms for graph routing problems
   • Abstract: In this talk we will focus on some of the central graph routing problems. We will survey known approximation algorithms and hardness of approximation results for these problems, including some recent developments. We will also highlight the major remaining open problems in the area of graph routing.


2. 10-10:20: Prof. David Mount:
   • Title: Polytope Approximation and the Mahler Volume
   • Abstract: The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in R^d, the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error eps. A worst-case optimal bound was given by Dudley (1974) and Bronshteyn and Ivanov (1976), who showed that in spaces of fixed dimension, O((diam(K)/eps)^{(d-1)/2}) vertices (alt., facets) suffice. We strengthen the above bound to roughly O(sqrt{area(K)}/eps^{(d-1)/2}). This is never worse than the previous bound and may be significantly better for skinny bodies. We also show how this result provides improvements to the best known search times for a pproximate nearest neighbor searching in spaces of fixed dimension. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume.
   
   
3. 11:00-11:20: Prof. Jonathan Katz:
   • Title: Completely Fair Protocols for Secure Computation
   • Abstract: Consider a protocol that allows one party holding x and a second party holding y to jointly compute the result f(x,y). Such a protocol is completely fair if either both parties learn f(x,y), or else neither party learns (any information about) the result, even if one party aborts the protocol early. Are completely fair protocols possible? Since the work of Cleve (1986) the general consensus has been that no non-trivial functions could be computed with complete fairness. Recently, we showed that this folklore belief is wrong.
     This talk will contain a high-level summary of this result; no cryptographic background is assumed. (In fact, the main problem can be stated in terms of information theory without any reference to cryptography or secure computation.)
   
   
4. 11:25-11:45: Prof. Samir Khuller:
   • Title: Combinatorial Algorithms for Online Structured Prediction
   • Abstract: Algorithms designers have (for the most part) always made the assumption that the input is accurately represented, and we wish to develop efficient algorithms to compute a desired subgraph with some properties (the subgraph could be required to be a min weight spanning tree, or a shortest path, or something else). In certain contexts the input may be erroneous and we may need to *modify* the input itself to ensure that a certain desired subgraph have some properties. How do we do this? In this work we show how to achieve this goal for several basic graph problems.
     (Joint work with Hal Daume and Greg Sanders.)


5. 11:50-12:10: Prof. MohammadTaghi Hajiaghayi:
   • Title: Minimizing Movement: Approximability and Fixed Parameter Tractability
   • Abstract: We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. This general family of movement problems encompass an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability and fixed-parameter tractability. These problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general set up and fortunately show that many movement problems of interest can be solved efficiently. On the other hand, we give approximation algorithms and inapproximability results for some classes of movement problems. In some cases, we obtain tight approximation and inapproximability results assuming P != NP.
   
   
6. 1:30-2:30: Distinguished Invited Speaker: Prof. Venkatesan Guruswami, Carnegie-Mellon University:
   • Title: Linear-algebraic list decoding and subspace-evasive sets
   • Abstract: This talk will describe a linear-algebraic approach to list decoding variants of Reed-Solomon codes. The algorithm is able to correct an error fraction approaching the information-theoretically maximum limit of 1-R where R is the rate of the code.
     The algorithm can be thought of as a higher-dimensional version of the Welch-Berlekamp decoder, and pins down the candidate solutions to a low-dimensional subspace. By pre-coding the messages to belong to an (explicitly or pseudorandomly) constructed "subspace-evasive set" that has small intersection with subspaces of the sort output by the decoder, one can prune the subspace to a small list of close-by codewords in polynomial time.
     This approach is quite versatile, and applies to list decoding folded Reed-Solomon codes (the context where it was first discovered), Reed-Solomon codes themselves when evaluation points lie in a subfield, algebraic-geometric codes (yielding efficiently list-decodable codes with simultaneously near-optimal rate, list size, and alphabet size), and Gabidulin codes (the rank-metric analog of Reed-Solomon codes). The talk might briefly discuss some of these variants.
     Based on joint works with Carol Wang and Chaoping Xing.


7. 3:00-3:20: Prof. Elaine Shi:
   • Title: Oblivious Storage Made Simple
   • Abstract: Oblivious storage is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. Despite two and a half decades of theoretic research on oblivious storage, to date, oblivious storage is still largely considered as costly and impractical for real-world applications.
     In this talk, I will propose a fundamentally novel paradigm for constructing oblivious storage. This new paradigm yields an extremely simple oblivious storage construction with only 30 lines of pseudo-code, and desirable worst-case asymptotic performance (with very small constants). Our construction has been implemented in several research prototypes developed by other research groups, and shown to have reasonable practical performance. This represents an important step forward in making oblivious storage practical.


8. 3:25-3:45: Prof. Bill Gasarch:
   • Title: The Complexity of Grid Problems
   Abstract: A c-coloring of the n x m grid is a mapping of {1,...,n} x {1,..,m} into {1,...,c} such that no four corners forming a rectangle have the same color. In 2009 a challenge went out to find a 4-coloring of the 17 x 17 grid. Such a coloring was found; however, the problem seemed to be difficult. This leads to the intuition that grid coloring is difficult in general. We have obtained two results that give evidence for this intuition: (1) Consider the following problem: given a partial c-coloring of an n x m grid, can it be extended to a full c-coloring? We show this problem is NP-complete. (2) The statement ``The n x m grid is c-colorable'' can be expressed as a Boolean formula with nmc variables. We show that if the n x m grid is not c-colorable then any tree resolution proof of the corresponding Boolean formula requires size exponential in c.


9. 3:50-4:10: Prof. Aravind Srinivasan:
   • Title: Constraint Satisfaction and the Lovász Local Lemma
   • Abstract: We consider a family of constraint-satisfaction problems with assignment constraints as well as a collection of decreasing Boolean constraints. Motivated by the proof ideas behind the Lovász Local Lemma and certain correlation inequalities, we present a sufficient condition for all these constraints to be simultaneously satisfiable. Our randomized method is nonconstructive; one intriguing difference with the Local Lemma is that many of our "bad" events will have probabilities very close to 1. Packet routing and other applications will also be discussed briefly.
     This is joint work with David Harris.