IBM®
Skip to main content
    United States [change]    Terms of use
  
 
 
    Home    Products    Services & solutions    Support & downloads    My account    
IBM Research

(none)

Activity Report


  Activity Report, July - December 2006
clear image

Highlights

Computational and structural dichotomies in the connectivity of Boolean satisfiability problems
Recent work on heuristics for random Boolean satisfiability problems has centered around the structure and connectivity of the solution space. Motivated by this work, Parikshit Gopalan (Georgia Tech), Phokion Kolaitis, Elitza Maneva and Christos Papadimitriou (UC Berkeley) study connectivity properties of the space of solutions of Boolean satisfiabilityproblems, and establish both computational and structural dichotomies in Schaefer's framework. Their results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side - which includes but is not limited to all problems with polynomial time algorithms for satisfiability - is in PTIME for the st-connectivity question, and in co-NP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear. The crux of these results is an expressibility theorem showing that a large class of Boolean constraint satisfaction problems can be reduced to each other in a way that preserves the structural properties of the solution space. These results were presented at the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006).

Efficient aggregation algorithms for probabilistic data
A crucial problem in probabilistic databases is to compute aggregation operators such as SUM, COUNT, AVERAGE, and MIN/MAX in an I/O efficient manner. Erik Vee (curently at Yahoo!), T.S. Jayram, and Satyen Kale (Princeton) give a generalization of the classical data stream model to handle probabilistic data, called probabilistic streams, in order to analyze the I/O-requirements of the algorithms. They present deterministic algorithms for several aggregation operators including novel algorithms for MIN, MAX, and AVERAGE. For MIN and MAX, the algorithms are one-pass and use space O(1/eps) to estimate within relative error eps. For AVG, their algorithm uses a novel technique based on generating functions and numerical integration to obtain a O(log n)-pass algorithm with space O(1/eps^2). They also prove tight linear-space lower bounds for exact computation. A paper describing these results was presented at the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).

Estimating the sortedness of a data stream
The distance to monotonicity of a sequence is the minimum number of edit operations required to transform the sequence into an increasing order; this measure is complementary to the length of the Longest Increasing Subsequence (LIS). Parikshit Gopalan (Georgia Tech), T.S. Jayram, Robert Krauthgamer and Ravi Kumar (Yahoo!) addressed the question of estimating these quantities in the one-pass data stream model and presented the first sub-linear space algorithms for both problems. Their main result is a randomized data-stream algorithm that, using only O(log^2 n) space, approximates the distance to monotonicity within a factor that is arbitrarily close to 4. A paper describing these results was accepted for presentation at the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).

On approximate Nash equilibrium
The computation of Nash equilibria in two-player normal form games is an important, and, in a technical sense, hard question. Konstantinos Daskalakis (UC Berkeley), Aranyak Mehta and Christos Papadimitriou (UC Berkeley) study the following question: How good an approximate Nash equilibrium can we find in polynomial time? They provide the first non-trivial polynomial time approximation algorithms for two standard notions of approximate equilibria, and also show connections to a well-studied conjecture in extremal graph theory. A paper describing these results appeared in the 2nd International Workshop on Internet and Network Economics (WINE 2006).

Awards and Honors

R. Fagin won an IBM Bravo Award for Sustained Contributions to Invention Disclosure Evaluation.

T.S. Jayram, 2nd Plateau Patent Award.

T.S. Jayram was awarded a mini-sabbatical, which he spent visiting the University of Washington in October 2006. Jayram is the first recipient of the new mini-sabbatical program for researchers at the Almaden Research Center.

V. Markl , P. Haas, N. Megiddo, M. Kutsch, T.M. Tran, and U. Srivastava won a 2005 IBM Pat Goldberg Memorial Best Paper Award for the paper "Consistently Estimating the Selectivity of Conjuncts of Predicates" which appeared in the Proceedings of the VLDB 2005 conference.

N. Megiddo, 14th Plateau Patent award, November 2006.


Publications and Conferences

Z. Bar-Yossef, Y. Birk, T. S. Jayram and T. Kol. Index Coding with Side Information. In Proc. 47th FOCS, pp. 280-289, October 2006.

D. Burdick, P. M. Deshpande, T. S. Jayram, R. Ramakrishnan, and S. Vaithyanathan. Efficient Allocation Algorithms for OLAP Over Imprecise Data. In Proc. VLDB 2006, pp. 391-402.

D. Chakrabarty, A. Mehta, V. Vazirani. Design is as easy as Optimization, In Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 4051: 477-488 Springer, 2006.

C. Daskalakis, A. Mehta, and C. Papadimitriou. A note on Approximate Nash equilibrium. In Proc. 2nd International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 4286, pp. 297-306, Springer 2006.

R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee, Comparing partial rankings. SIAM J. Discrete Mathematics 20, 3, 2006, pp. 626-648

P. Gopalan, P. Kolaitis, E. Maneva and C. Papadimitriou. Computing the Connectivity Properties of the Satisfiability Solution Space, In Proc. of 33rd ICALP, pp.346-357, 2006.

T. S. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, H. Zhu. Avatar Information Extraction System. IEEE Data Eng. Bull. 29(1): 40-48, 2006.

H. Jin and J. Lotspiech and N. Megiddo. Efficient Traitor Tracing, IBM Research Report RJ-10390, 10/03/2006.

R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In Proceedings of 47th FOCS, October 2006.

R. Krauthgamer and M. Charikar. Embedding the Ulam metric into l_1. Theory of Computing (ToC), 11(2):207-224, 2006.

M. Kutsch, P. Haas, V. Markl, N. Megiddo, and T. M. Tran. Integrating a Maximum-Entropy Cardinality Estimator Into DB2 UDB, In Proc. of EDBT 2006, pp. 1092-1096.

V. M. Kutsch, T. M. Tran, P. Haas and N. Megiddo. MAXENT: Consistent Cardinality Estimation in Action. In Proc. of SIGMOD 2006, pp. 775-777.

E. Maneva, and A. Shokrollahi. New Model for Rigorous Analysis of LT codes, In Proc. of ISIT 2006, pp.2677-2679.

V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava and T. M. Tran. Consistent selectivity estimation vis maximum entropy. The VLDB Journal, 16, pp. 55-76, 2007.

U. Srivastava P. Haas, V. Markl, N. Megiddo, M. Kutsch and T. M. Tran. ISOMER: Consistent Histogram Construction Using Query Feedback. In Proc. of ICDE 2006.

Patents

N. Megiddo, Method for solving stochastic control problems of linear systems in high dimension, Issued as patent 7,117,130 in US, 10/3/2006.

T. Kimbrel, R. Krauthgamer, B. Schieber, M. Sviridenko, J. Thathachar, M. Minkoff. Dynamic resource allocation using known future benefits, Issued as patent 7,085,837 in US, 8/1/06.

J.P. Bigus, J.L. Hellerstein, S. Parekh, J.R. Pilgrim, D.A. Schlosnagle, M.S. Squillante, and J.S. Thathachar. Object-Oriented Framework for Generic Adaptive Control, Issued as patent 7,120,621 in US.

A. Garg, J.S. Thathachar, S. Vaithyanathan, and H. Zhu. Method To Hierarchical Pooling Of Opinions From Multiple Sources, Issued as patent 7,130,777 in US.

Invited Talks

  • P. Kolaitis
    Invited Lecturer, Bertinoro PhD School on Data and Service Integration (DASI '06), 
    Bertinoro, Italy, December 2006.
  • R. Krauthgamer
    On embedding edit distance into l_1. Concentration week on Metric Geometry and Embeddings,
    Texas A&M, July 2006.
  • E. Maneva
    The Connectivity of Boolean Satisfiability: Structural and Computational Dichotomies.
    Dagstuhl seminar on Complexity of Constraints, Germany, October 2006.
    Survey Propagation Algorithm.
    Dagstuhl Seminar on Complexity of Constraints, Germany, October 2006.
  • A. Mehta
    Design is as easy as Optimization.
    Bay Area Theory Seminar (BATS), IBM Almaden, December 2006.

Presentations and Seminars
  • R. Fagin
    "Operators on schema mappings"
    Stanford Logic Group, July 2006
  • T.S. Jayram
    "Aggregating Imprecise Data in OLAP: Principles and Algorithms"
    University of Washington, CSE Department Colloquium, October 2006.
    "Index Coding with Side Information"
    University of Washington, October 2006.
    "The Avatar Information Extraction System"
    Stanford Technical Meeting on Uncertain/Probabilistic Data, September 2006.
  • R. Krauthgamer
    "A metric notion of dimension and its algorithmic applications"
    IBM Watson TheoryFest, July 2006.
    "Algorithms for edit distance on permutations"
    UC Berkeley, October 2006, and Stanford University, October 2006.
    "On embedding edit distance into l_1"
    The Hebrew University, Jerusalem, Israel, December 2006.
  • E. Maneva
    "Algorithms and thresholds for random SAT: from a physical theory to a combinatorial picture"
    UC Berkeley, November 2006.
  • A. Mehta
    "Adwords and generalized online matching"
    New York University, November 2006, and Johns Hopkins University, October 2006.
    "Design is as easy as Optimization"
    Georgia Tech, September 2006; MIT, October 2006; and DIMACS-Princeton Mixer, November 2006.

Committee Work
  • P. Kolaitis
    Program committe member, 2007 International Database Theory Conference (ICDT 2007)
    Co-organizer, Dagstuhl Workshop on Complexity of Constraints, October 2006
    NSF Panel Member, CISE, August 2006

Editorships

External Positions

Miscellaneous

R. Fagin and R. Krauthgamer attended the IBM Watson Theory Fest workshop, July 23-28, 2006

R. Krauthgamer served as the local organizer for the 2006 Bay Area Theory Symposium that was held in IBM Almaden on December 1, 2006.

N. Megiddo served as a guest editor for a special issue of Theoretical Computer Science.

Personnel

Short-Term Visitors
  • Amit Charkrabarti (Aug. 14 - 25, 2006)
  • Tim Roughgarden (Sep. 5 - 22, 2006)
  • Atri Rudra (Oct. 25 - 27, 2006)
  • Alex Andoni (Oct. 30 - Nov. 1, 2006)
Transitions (in chronological order)
  • Erik Vee completed his postdoc in August 2006 and joined Yahoo! Research as a postdoc.
  • Elad Hazan, a recent graduate of Princeton University, joined the department as a Research Staff Member in September 2006.
  • Elitza Maneva, a recemt graduate of UC Berkeley, joined the department as a postdoc in October 2006.
  • Alan Nash, a recent graduate of UC San Diego, joined the department as a Research Staff Member in October 2006.
Organization
  • Phokion Kolaitis, Senior Manager, CS Principles and Methodologies
  • Christina Howell (Administrative Assistant)
  • Ron Fagin, Manager, Foundations of Computer Science
  • Miki Ajtai
  • Elad Hazan
  • T. S. Jayram
  • Robert Krauthgamer
  • Nimrod Megiddo
  • Elitza Maneva
  • Aranyak Mehta
  • Alan Nash

    About IBM    Privacy    Contact