Skip to main content

Activity Report

Activity Report, January - June 2006


Highlights

Bag-containment of conjunctive queries
The containment problem for conjunctive queries (sometimes known as SELECT-PROJECT-JOIN queries) is a fundamental problem in query optimization. In many query processing languages, e.g. SQL, queries return multisets,or bags, of answers. Despite this, much of the work on query containment treats queries as returning sets. T.S. Jayram, Phokion Kolaitis, and Erik Vee study the bag-containment question, where queries are treated as returning bags of tuples. In their study of the problem, they developed several major insights on the problem and they showed that determining whether one conjunctive query with inequalities is bag-contained in another such query is an undecidable problem. The results were presented at the 25th ACM Symposium on the Principles of Database Systems (PODS 2006).

Inverting schema mappings
A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). Although the notion of an inverse of a schema mapping is important, the exact definition of an inverse mapping is somewhat elusive. This is because a schema mapping may associate many target instances with each source instance, and many source instances with each target instance. Based on the notion that the composition of a mapping and its inverse is the identity, Ron Fagin gave a formal definition for what it means for a schema mapping M' to be an inverse of a schema mapping M for a class S of source instances. If S is the class of all source instance, then M' is a "global inverse" of M. Ron gave a construction that produces a global inverse if one exists. This work appeared in the 2006 ACM Symposium on Principles of Database Systems (PODS'06).

Design is as easy as optimization
Deeparnab Chakrabarty (Georgia Tech), Aranyaj Mehta and Vijay Vazirani (Georgia Tech) established a theorem that takes an approximation algorithm for optimization and transfers it to an algorithm for design problems, while preserving the algorithm's approximation guarantee. This transfer is a black-box and efficient reduction, and generalizes several such transfer theorems known for individual problems. This work was accepted to the 33rd International Colloquium on Automata, Languages and Programming (ICALP'06).

Algorithms on negatively curved spaces
In recent years, the study of finite metric spaces have become a powerful tool in an algorithm designer's arsenal, and the techniques developed are extremely useful in different contexts, such as combinatorial optimization, networking, and data analysis. Robert Krauthgamer and James R. Lee (IAS, Princeton) initiate the study of approximate algorithms for negatively curved metric spaces, which seem to arise naturally in various domains of computer science including networking and vision. They give efficient algorithms and data structures for problems like approximate near-neighbor search and compact, low-stretch routing on subsets of negatively curved spaces of fixed dimension (including, e.g. $H^2$ as a special case). The classical example of such a space is the real-hyperbolic space H^2, but their algorithmic approach applies to a more general family of spaces characterized by Gromov's (combinatorial) hyperbolic condition [Essays in group theory, 1987]. In a different direction, they show that there is a polynomial time approximation scheme (PTAS) for the traveling salesman problem (TSP) when the set of cities lie, for example, in H^2. This generalizes Arora's results [JACM, 1998] for the Euclidean plane R^2. A paper describing these results was accepted to the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06).

Towards secure and scalable computation in peer-to-peer networks
One of the challenges in designing peer-to-peer systems is robustness to various failures, especially when the number of peers is extremely large. Although peer-to-peer systems have been well-studied, there has been relatively little formal work on robust scalable systems. Valerie King (University of British Columbia), Jared Saia (University of New Mexico), Vishal Sanwalani (University of New Mexico), and Erik Vee tackle this issue by designing new leader-election and Byzantine agreement protocols in which the total communication for each peer is only polylogarithmic in the number of participants. The protocol is designed to sustain peers that have been adversarially corrupted (up to 1/3 of the peers). Furthermore, extending previous work, this protocol functions even on fixed networks of polylogarithmic degree. A paper describing these results was accepted to the 47th IEEE Foundations of Computer Science (FOCS 2006).

Index coding with side information
Consider the following coding problem, which is motivated by a problem of transmitting data over broadcast channels: a sender wishes to communicate an input x of length n over a broadcast channel with n receivers so that the i-th receiver R_i can recover the i-th bit of x. Each R_i has prior side information about x, induced by a directed graph G on n nodes; R_i knows the bits of x in the positions {j | (i,j) is an edge of G}. Encoding schemes that achieve this goal will be called INDEX codes with side information graph G. Ziv Bar-Yossef (Technion, Israel), Yitzhak Birk (Technion, Israel), T.S. Jayram, and Tomer Kol (Technion, Israel) identify a measure on graphs, the minrank, which they conjecture to exactly characterize the minimum length of INDEX codes. They resolve the conjecture for certain natural classes of graphs. For arbitrary graphs, they show that the minrank bound is tight for both linear codes and certain classes of non-linear codes. For the general problem, they obtain a (weaker) lower bound that the length of an INDEX code for any graph G is at least the size of the maximum acyclic induced subgraph of G. A paper describing these results was accepted to the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06).

Awards and Honors

M. Ajtai, appointed Honorary Research Fellow of the Alfred Renyi Mathematical Research Institute of the Hungarian Academy of Sciences, May 2006.

R. Fagin, P. Kolaitis, and L. Popa won an IBM Outstanding Innovation Award for "Foundations of Schema Mappings".

R. Fagin, P. Kolaitis, and L. Popa's work on "Foundations of schema mappings" was named as an IBM Research Division Accomplishment for 2005.



Publications and Conferences

S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, On the hardness of approximating multicut and sparsest-cut, Computational Complexity 15(2), pp. 94-114, 2006.

R. Fagin, Inverting schema mappings, Proc. 25th ACM Symposium on Principles of Database Systems, Chicago, 2006. Invited to special issue of ACM Trans. on Database Systems for selected papers from the conference.

R. Fagin, P. G. Kolaitis, L. Popa, Wang-Chiew Tan, Composing schema mappings: second-order dependencies to the rescue, ACM Transactions on Database Systems, 30(4), pp. 994-1055.

U. Feige and R. Krauthgamer, A polylogarithmic approximation of the minimum bisection, SIAM review 48(1), pp. 99?130, 2006.

T.S. Jayram, P. G. Kolaitis, E. Vee, The containment problem for "real" conjunctive queries with inequalities, Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS 2006), pp. 80-89, June 2006.

H. Karloff, S. Khot, A. Mehta and Y. Rabani, On Earthmover Distance, Metric Labeling and 0-Extension, Proceedings of 38th ACM Symposium on Theory of Computing (STOC 2006), pp. 547-556, May 2006.

V. King, J. Saia, V. Sanwalani, and E. Vee, Scalable Leader Election. Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 990-999, January 2006.

P. G. Kolaitis, J. Panttaja, W.-C. Tan, The complexity of data exchange, Proceedings of the Twenty-Fifth ACM Symposium on Principles of Database Systems (PODS 2006), pp. 30-39, June 2006.

R. Krauthgamer and Y. Rabani, Improved lower bounds for embeddings into L1. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1010-1017, January 2006.

Patents

N. Megiddo, "Massively computational parallizable optimization management system and method", Issued as patent 7013344 in US, 3/14/2006.

N. Megiddo, "System, method and program product for automatically managing contracts", Issued as patent 6985868 in US, 1/10/2006.

N. Megiddo and D. Modha, "System and method for implementing an adaptive replacement cache policy", Issued as patent 6996676 in US, 2/7/2006.

N. Megiddo and S. Vaithyanathan, "System and method for gathering, indexing, and supplying publicly available data charts", Issued as patent 6996268 in US, 2/7/2006.

Invited Talks

  • R. Fagin
    "Operators on schema mappings" Keynote speech at Second International Workshop on Exchange and Integration of Data, June 9, 2006
  • P. Kolaitis
    "Foundations of Schema Mappings" Invited Tutorial, Workshop on Logic and Databases, Isaac Newton Institute for the Mathematical Sciences, Cambridge, UK, March 2006
    "Constraint Satisfaction and Logic" Invited Tutorial, Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory, University of Oxford, UK, March 2006
  • R. Krauthgamer
    "Algorithms on negatively curved spaces" Workshop on Approximation Algorithms, CRM, Universite de Montreal, Canada, June 2006

Presentations and Seminars

  • R. Fagin
    "Composing schema mappings: second-order dependencies to the rescue" Stanford Logic Group, March 2006
  • R. Krauthgamer
    "Algorithms on negatively curved spaces" UC Berkeley, May 2006
  • A. Mehta
    "Design is as easy as optimization" Stanford University Theory Seminar, April 2006 "On the Fourier Spectrum of Symmetric Boolean Functions" UC Berkeley Theory Seminar, May 2006

Committee Work

  • R. Fagin
    Program committee member, Flexible Query Answering Systems, 2006 Program committee member, International World Wide Web Conference, 2006

Editorships


External Positions


Personnel

Short-Term Visitors

  • Daniela Pucci de Farias (Jan 31 - Feb 3, 2006)
  • Jeremy Schwartz (Jan 31 - Feb 3, 2006)
  • Miahi Patrascu (Apr 26 - May 1, 2006)
  • Matt Valeriote (June 5-10, 2006)


Organization

  • Phokion Kolaitis, Senior Manager, CS Principles and Methodologies
  • Christina Howell (Administrative Assistant)
  • Ron Fagin, Manager, Foundations of Computer Science
  • Miki Ajtai
  • T. S. Jayram
  • Robert Krauthgamer
  • Nimrod Megiddo
  • Aranyak Mehta
  • Erik Vee


Transitions

  • Christina Howell joined the department as an administrative assistant in March 2006.

Activity Reports