Highlights
Information Statistics and Communication Complexity Lower Bounds
Ziv
Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar present a new method for
proving strong lower bounds in communication complexity. This method is based on
the notion of the conditional information cost of a general
communication protocol, which measures the amount of information revealed by the
transcript about the inputs. While conditional information cost is a lower bound
on the communication complexity, we show that it also admits a direct sum
theorem. The direct sum decomposition reduces the task to that of proving
lower bounds for simple problems (such as AND of two bits). For the latter, they
develop a novel technique based on Hellinger distance and its generalizations.
Their paradigm leads to two main results:
(1) An improved lower bound for
the multi-party set-disjointness problem in the general communication model, and
a nearly optimal lower bound in the one-way communication model. Consequently,
approximating the k-th frequency moment for real k > 2 in the data stream
model requires at least n^{1 - 2/k} space, resolving a conjecture of Alon,
Matias, and Szegedy [STOC 96].
(2) A lower bound for the L_p approximation
problem in the general communication model. This solves an open problem of Saks
and Sun [STOC 02]. Consequently, approximating the L_p norms for p > 2 to
within a factor of n^{epsilon} in the data stream model with constant number of
passes requires at least n^{1 - 4epsilon - 2/p} space.
A paper will appear
in the 43rd Symposium on Foundations of Computer Science (FOCS 2002).
Algorithm to Count Distinct Elements in a Data Stream
The
zeroth-frequency moment of a sequence of elements is the number of
distinct elements that occur in the sequence. Counting the number of distinct
elements is a fairly fundamental problem in databases. Ziv Bar-Yossef, T. S.
Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan (UC Berkeley) present three
space- and time-efficient algorithms for approximating the zeroth-frequency
moment of a sequence of elements in the data stream model. Their algorithms
improve upon known algorithms for this problem and offer a spectrum of
time/space tradeoffs. A paper will appear in the 6th Intl. Workshop on
Randomization and Approximation Techniques in Computer Science (RANDOM 2002).
Faster Approximation Algorithms for the Minimum Latency Problem
Aaron
Archer (Cornell University) and David Williamson have devised faster
approximation algorithms for the minimum latency problem (MLP). The MLP is a
version of the traveling salesman problem in which one wants to minimize the
average time each node is visited, rather than the total time for visiting all
nodes. All known approximation algorithms for MLP call a subroutine for the
k-MST problem, which in turn calls a subroutine for the prize-collecting Steiner
tree problem (PCST). The best previously known algorithms achieve an
approximation factor of 10.77 with O(n^2 log n) PCST calls, or 7.18 + x with
O(n^{1/x}) PCST calls. They achieve a factor of 9.28 with O(n log n) PCST calls.
To achieve a similar factor, previous algorithms required at least Omega(n^4)
times more PCST calls. A paper with this algorithm was submitted to the 2003
ACM-SIAM Symposium on Discrete Algorithms (SODA).
Awards and Honors
R. Fagin was selected as a "Highly
Cited Researcher" by ISI. Individuals cited by ISI are the most highly cited
within their field during 1981-1999, and comprise less than one-half of one
percent of all publishing researchers.
R. Fagin received an IBM Outstanding Innovation Award for Aggregation
Algorithms for Middleware.
R. Kumar, S. Rajagopalan, and A. Tomkins received IBM Outstanding Innovation
Awards for Web Graph Structure.
D. Gibson, R. Kumar, S. Rajagopalan, and A. Tomkins received IBM Research
Division Awards for HITS/CLEVER.
N. Megiddo, Invention Achievement Award, Eleventh Plateau, Jan. 2002
Publications and Conferences
M. Ajtai, The
invasiveness of off-line memory checking, Proc. 34th ACM Symp. on Theory
of Computing, May 2002, pp. 504-513.
M. Ajtai, T. S. Jayram, R. Kumar, and D. Sivakumar, Approximate counting of
inversions in a data stream, Proc. 34th ACM Symp. on Theory of
Computing, May 2002, pp. 370-379.
M. Ajtai, R. Kumar, and D. Sivakumar, Sampling short lattice vectors and the
closest lattice vector problem, Proc. 17th IEEE Conf. on Computational
Complexity, May 2002, pp. 53-57.
T. Asano and D. P. Williamson, Improved approximation algorithms for MAX SAT,
Journal of Algorithms 42 (2002), pp. 173-202.
Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar, Information theory
methods in communication complexity, Proc. 17th IEEE Conf. on
Computational Complexity, May 2002, pp. 93-102.
Z. Bar-Yossef, R. Kumar, and D. Sivakumar, Reductions in streaming
algorithms, with an application to counting triangles in graphs, Proc.
13th ACM-SIAM Symp. on Discrete Algorithms, Jan. 2002.
T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld, The complexity of
estimating the entropy, Proc. 34th ACM Symp. on Theory of
Computing, May 2002, pp. 678-687; also, Proc. 17th IEEE Conf. on
Computational Complexity, May 2002, p. 17.
C. Dwork and L. Stockmeyer, 2-round zero knowledge and proof auditors,
Proc. 34th ACM Symp. on Theory of Computing, May 2002.
R. Fagin, Combining fuzzy information: an overview, SIGMOD
Record 31, 2, (2002), pp. 109-118.
R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld,
M. Sudan, and A. Tomkins, Random walks with "back buttons", Annals of
Applied Probability 11, 3 (2001), pp. 810-862.
C.-T. Ho and L. Stockmeyer, A new approach to fault-tolerant wormhole routing
in mesh-connected parallel computers, Proc. Intl. Parallel and Distributed
Processing Symp., April 2002.
J. Rao, C. Zhang, G. Lohman, and N. Megiddo, Automating physical database
design in a parallel database, ACM SIGMOD/PODS, June 2002.
R. Ravi and D. P. Williamson, Erratum: An approximation algorithm for
minimum-cost vertex-connectivity problems, Algorithmica 34 (2002),
pp. 98-107.
L. Stockmeyer and D. S. Modha, Links between complexity theory and
constrained block coding, IEEE Trans. on Information Theory, 48
(2002), pp. 59-88.
D. P. Williamson, The primal-dual method for approximation algorithms,
Mathematical Programming 91 B (2002), pp. 447-478.
Patents
M. Ajtai, R.C. Burns, R. Fagin, and L.J.
Stockmeyer, System and Method for Differential Compression of Data from a
Plurality of Binary Sources, Issued as Patent 6374250 in US, 04/16/2002.
S. Chakrabarti, B.E. Dom, D.A. Gibson, P. Raghavan, S. Rajagopalan, S.
Ravikumar, and A.S. Tomkins, Method for Interactively Creating an Information
Database Including Preferred Information Elements, Such As Preferred-Authority,
World Wide Web Pages, Issued as Patent 6336112 in US, 01/01/2002.
B.G. Lindsay, G.S. Manku, and S. Rajagopalan, Single Pass Space Efficient
System and Method for Generating an Approximate Quantile in a Data Set Having an
Unknown Size, Issued as Patent 6343288 in US, 01/29/2002.
Invited Talks
- R. Kumar
"Simple exponential algorithms for SVP and CVP," Contemporary
Methods in Cryptography, Institute for Pure and Applied Mathematics, UCLA,
Jan. 2002.
Presentations and Seminars
- R. Fagin
- "Easier ways to win logical games,"
- Symposium on the Effectiveness of Logic in Computer Science,
Saarbruecken, Germany, March 2002.
- ARC, March 2002.
- R. Kumar
- "Approximating the number of inversions in a data stream,"
- Cornell University, Feb. 2002.
- "Rank aggregation methods for the Web,"
- NEC Research Institute, Feb. 2002.
- T. S. Jayram
- "Algorithms for counting inversions,"
- University of Maryland, Feb. 2002.
- "An information statistics approach to data stream and communication
complexity,"
- UC Berkeley, May 2002.
- Workshop on Branching Programs, McGill University, May 2002.
- D. Williamson
- "Approximation algorithms for MAX 3-CUT and other problems via complex
semidefinite programming,"
- Sixth Aussois Workshop on Combinatorial Optimization, Jan. 2002.
- Carnegie Mellon University, March 2002.
Committee Work
- R.Fagin
Program committee member, ACM Symposium on Principles of
Database Systems (PODS), 2002.
Program committee member, Workshop on Distributed Data and
Structures, 2002.
- R. Kumar
Program committee member, 2nd International Workshop on Web
Dynamics, 2002.
- T. S. Jayram
Review panel member, NSF, Washington D.C.
- D. Williamson
Program committee member, 9th International Conference on
Integer Programming and Combinatorial Optimization (IPCO).
Editorships
- R. Fagin
Chicago Journal of Theoretical Computer Science
Journal of
Computer and System Sciences
Methods of Logic in Computer Science
- N. Megiddo
Area editor, Journal of the
ACM
Area editor, Mathematics of Operations Research
Area editor, Operations Research
Letters
Editorial Board Member, Algorithmica
Editorial Board Member, Discrete
Applied Mathematics
Editorial Board Member, Games and Economic Behavior
Editorial Board Member, Journal of Combinatorial
Optimization
Associate Editor, Mathematical
Programming
- D. Williamson
Associate Editor, Journal of Algorithms
Associate Editor,
Mathematics of Operations Research
Associate Editor, SIAM Journal on
Computing
Associate Editor, SIAM Journal on Discrete Mathematics
Editorial Board member, MPS/SIAM Book Series on Optimization
External Positions
Miscellaneous
N. Megiddo taught the course
Network and Integer Programming (MS&E 212) at Stanford University.
Personnel
Transitions
Ziv Bar-Yossef joined the
department, July 2002. He is a recent graduate of UC Berkeley.
Jim Hafner is on a two-year leave to work with the Storage Attachment project
at ARC.
Organization
David Williamson (Manager) CS Principles and Methodologies
Sally Floyd (Administrative Assistant)
Jim Hafner (On Leave)
Andrew Tomkins (Manager) Information Management Principles
Ziv Bar-Yossef
David Gibson
Ravi Kumar
Kevin McCurley
Sridhar Rajagopalan
John Tomlin (Assignee)
Ron Fagin (Manager) Foundations of Computer Science
Miki Ajtai
T. S. Jayram
Nimrod Megiddo
D. Sivakumar
Larry Stockmeyer
|
