Highlights
Modeling and Reusing Results of Generic Schema-Matching Algorithms
It has been shown previously that the task of schema integration can benefit
from the reuse of a history of matchings and mappings. The more accurate the
automatic matchings between elements of two schemas are, the less is the load on
the manual part of the integration task. Elitza Maneva and Roxana Stanoi have
developed a new method for modeling correlations between correspondences output
by schema matching algorithms. The objective is to be able to reuse such
information efficiently, in order to avoid re-running computationally expensive
schema-matching algorithms. The method makes use of a probabilistic graphical
model that is commonly used in the area of machine learning. Optimal and
heuristic algorithms for different settings were developed for a particular
application of the model, namely that of finding top k mappings.
Random SAT, Shelling Processes and Convex Geometries
In studying the phase transitions exhibited by random satisfiability problems,
researchers have recently been led to questions about the structure of the space
of solutions of the random instances of these problems. In particular, the
performance of the survey propagation algorithm, which is the state-of-the art
algorithm for random satisfiability, is tied to particular partial satisfying
assignments known as cores. Elitza Maneva and Alistair Sinclair (UC Berkeley)
have shown that random 3-SAT formulas of density above a certain constant either
are unsatisfiable or they do not have core assignments. This result implies
either an improvement in the current upper bound for the threshold of
satisfiability, or a refutation of a physical conjecture that is behind the
design of the survey propagation algorithm. The main technique is a novel
combinatorial identity for a certain type of removal processes. In related work,
Elitza Maneva and Federico Ardila (SFSU) have analyzed this identity in a more
general context, and discovered that it characterizes a combinatorial object
known as a convex geometry. These results will appear in Theoretical
Computer Science and Discrete Mathematics, respectively.
Tighter Bounds for Random Projections of Manifolds
The Johnson-Lindenstrauss random projection lemma gives a simple way to reduce
the dimensionality of a set of points while approximately preserving their
pairwise distances. The most direct application of the lemma applies to a finite
set of points, but recent work has extended the technique to affine subspaces,
curves, and general smooth manifolds. Ken Clarkson considered the case of random
projection of smooth manifolds and sharpened a previous analysis, reducing the
dependence on such properties as the manifold's maximum curvature. This paper
will appear in the Symposium on Computational Geometry, SoCG 2008.
Self-Improving Algorithms for Delaunay Triangulations
Ken Clarkson and summer intern Seshadhri Comandur studied the problem of
two-dimensional Delaunay triangulation in the self-improving algorithms model,
and devised an optimal algorithm in this setting. Here the n points of the input
are assumed to each come from an independent, unknown, and arbitrary
distribution. The first phase of their algorithm builds data structures that
store relevant information about the input distribution. The second phase uses
these data structures to efficiently compute the Delaunay triangulation of the
input, with a running time that matches the information-theoretic
lower bound for the output distribution. This implies that if the output
distribution has low entropy, then their algorithm beats the standard Omega(n
log n) bound for computing Delaunay triangulations. To appear in
the Symposium on Computational Geometry, SoCG 2008.
Adaptive Algorithms for Online Convex Optimization
Seshadhri Comandur and Elad Hazan describe a series of reductions, based upon
data streaming techniques, that transform algorithms for minimizing (standard)
regret into adaptive algorithms, albeit incurring only poly-logarithmic
computational overhead. Using this method, they obtain efficient low
adaptive-regret algorithms for the problem of general online convex
optimization.
Evolvability and Learning
Leslie Valiant has recently introduced a framework for analyzing the
capabilities and the limitations of the evolutionary process of random change
guided by selection. In his framework ,the process of acquiring a complex
functionality is viewed as a substantially restricted form of learning of an
unknown function from a certain set of functions. Valiant showed that classes of
functions evolvable in his model are also learnable in the statistical query
(SQ) model of Kearns that allows only the gathering of statistics about the unknown
function. Vitaly Feldman showed that evolvability is equivalent to learnability
by a restricted form of statistical queries. Based on this equivalence he proved
that for any fixed distribution D over the domain, every class of functions
learnable by SQs over D is evolvable over D. Previously, only the evolvability
of monotone conjunctions of Boolean variables over the uniform distribution was
known (Valiant, 2007). In addition, he gave a characterization of
distribution-independent evolvability that shows that evolvability is strictly
weaker than learning by statistical queries. These results were accepted for
presentation at the 40th ACM Symposium on Theory of Computing (STOC 2008).
Awards and Honors
The paper "Ocelot's knapsack calculations for modeling power amplifier and Walsh code limits",
by Ken Clarkson and John D. Hobby, appeared at VTC-2007-Fall, the fall 2007 IEEE Vehicular Technology Conference, where it won the Best Paper Award.
Ron Fagin was elected to the IBM Academy of Technology in October 2007 "for fundamental contributions to computer science theory and its application to IBM products"
Ron Fagin received an IBM Research Division Award ("Asset Award") in October 2007 for Compliance Auditing Asset.
The research on "Schema mappings: theory and practice", by Ron Fagin and Phokion Kolaitis;
joint with Lucian Popa, Howard Ho, Laura Haas, and Mauricio A Hernandez,
received an Upgrade to Outstanding Research Division Accomplishment, December 2007.
Nimrod Megiddo received the 15th Plateau Invention Achievement Award
Publications and Conferences
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toni Pitassi. The Complexity of Properly Learning Simple Concept Classes. Journal of Computer and System Sciences, 74(1), 2008, pp.16-34. Special issue on Learning Theory in 2004.
P. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. Proceedings of NIPS 2007.
Laura Chiticariu, Mauricio A. Hernandez, Lucian Popa and Phokion G. Kolaitis, Semi-Automatic Schema Integration in Clio (demo paper), Proceedings of the 33rd Very Large Databases Conference, (VLDB 2007), pp. 1326-1329.
K. Clarkson and J. D. Hobby. Ocelot's knapsack calculations for modeling power amplifier and Walsh code limits. In VTC-2007-Fall: IEEE Vehicular Technology Conference, 2007.
K. Clarkson, G. Hampel, and J. D. Hobby. Modeling uplink power control with outage probabilities. In VTC-2007-Fall: IEEE Vehicular Technology Conference, 2007. Accepted to IEEE Transactions on Wireless Communications.
Ron Fagin, Inverting schema mappings. ACM Trans. on Database Systems 32, 4, Nov. 2007. Special issue for selected papers from the 2006 ACM Symposium on Principles of Database Systems.
Vitaly Feldman. Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
Journal of Machine Learning Research, 8(Jul), 2007, pp.1431-1460. Special issue on Conference on Learning Theory 2005.
Vitaly Feldman, Shrenik Shah, and Neal Wadhwa. Separating Models of Learning with Faulty Teachers.
Proceedings of Algorithmic Learning Theory (ALT) Conference, 2007, pp. 94-106.
S. Kale and E. Hazan. Computational Equivalence of Fixed Points and No-Regret Algorithms, and Convergence to Equilibria, Proceedings of NIPS, 2007.
Phokion G. Kolaitis, Reflections on Finite Model Theory, Invited paper, Proceedings of the Twenty-second Annual IEEE Symposium on Logic in Computer Science, (LICS 2007), pp. 257-269
N. Megiddo and V. Vazirani, Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets, Proceedings of Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Lecture Notes in Computer Science 4858 Springer, 2007 pp. 362-367.
E. Maneva, E. Mossel, M. Wainwright, A New Look at Survey Propagation and its Generalizations, Journal of ACM, Volume 54(4) , pp. 2-41, 2007.
D. Woodruff and S. Yekhanin, A Geometric Approach to Information-Theoretic Private Information Retrieval, SIAM Journal of Computing, Volume 37(4), pp. 1046-1056, 2007.
Patents
A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, D. Woodruff, Algorithms for Transitive-Closure Spanners of Specific Graph Families." Filed as Docket ARC820070202, 12/07.
R. Fagin, P. Kolaitis, L. Popa, and W-C. Tan, "Quasi-inverses of schema mappings." Filed as Docket ARC920070055, 7/07
E. Hazan and N. Megiddo, "Method for Machine Learning with State Information."
G. Lohman, N. Megiddo, J.Rao, "Discovering Interestingness In Advanced Faceted Search." Filed 10/07.
D. Woodruff, "An Algorithm for Finding Sparse Directed Spanners, with Applications." Filed as Docket ARC820070201, 12/07
Presentations and Seminars
- K. Clarkson
- Core Sets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm
- CMU Computer Science Colloquium, September 2007 and
BATS, the Bay Area Theory Seminar, December 2007.
- K. Clarkson
- Tighter Bounds for Random Projections of Manifolds
- Stanford: presentation to Guibas Laboratories, November 2007 and UC Davis Computer Science Colloquium, December 2007.
- E. Hazan
- Recent Advances in Online Convex Optimization
- Princeton Theory Seminar, November 2007
- P. Kolaitis
- Reflections on Finite Model Theory
- Invited Talk, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), Wroclaw, Poland, July 2007.
- P. Kolaitis
- How can academia and industry work together to address educational issues?
- Invited Panel Presentation, Google, Education Summit, Mountain View, California, July 2007.
- P. Kolaitis
- Constraint Satisfaction, Complexity, and Logic
- Invited Colloquium Talk, University of Turku, Finland and University of Tampere, Finland, September 2007.
- P. Kolaitis
- Schema Mappings and Data Exchange
- Invited Colloquium Talk, University of Helsinki, Finland, September 2007.
- E. Maneva
- The Structure of Constraint Satisfaction Problems
- Statphys 23 Satellite Workshop on Statistical Mechanics of Distributed Information Systems, Finland, Jul 2007.
Committee Work
- E. Hazan
- Committee member for the Bay Area Theory Seminar (BATS), 2007.
- P. Kolaitis
- With Maurizio Lenzerini (University of Rome "La
Sapienza") and Arnold Rosenthal (MITRE), organized INFINT
2007, a workshop on information integration at Bertinoro,
Italy, September 30 to October 4, 2007. The workshop was
attended by approximately 25 invited participants who
interacted in a discussion-oriented format aiming to
formulate a vision and an agenda to tackle some of the key
challenges of information integration.
Editorships
- K. Clarkson
Associate Editor, Computational Geometry: Theory and Applications
Associate Editor, Operations Research Letters
- R. Fagin
Editor, Chicago Journal of Theoretical Computer Science
Associate Editor, Journal of Computer and System Sciences
Editorial Board Member, Foundations and Trends in Databases
- P. Kolaitis
Managing Editor, Annals of Pure and Applied Logic
Editor, Bulletin of Symbolic Logic
Associate Editor, ACM Transactions on Database Systems
Editorial Board Member, Journal of Logic and Computation
Editorial Board Member, Theory of Computing Systems
Editorial Board Member, International Journal of Foundations of Computer Science
Advisory Board Member, Logical Methods in Computer Science
- R. Krauthgamer
Associate Editor, Theory of Computing
- N. Megiddo
Editor-in-Chief, Mathematics of Operations Research
Area Editor, Journal of the ACM
Area Editor, Operations Research Letters
Editorial Board Member, Algorithmica
Editorial Board Member, Discrete Applied Mathematics
Editorial Board Member, Discrete Optimization
Editorial Board Member, Games and Economic Behavior
Editorial Board Member, Journal of Combinatorial Optimization
Associate Editor, Mathematical Programming
External Positions
- M. Ajtai
Honorary Research Fellow of the Renyi Institute of The Hungarian Academy of Sciences.
- P. Kolaitis
Foreign Member, Finnish Academy of Science and Letters.
- N. Megiddo
Member of the Scientific Board, The Institute for Medical BioMathematics, Israel.
Miscellaneous
K. Clarkson served on the Ph.D. thesis committee for Hubert Chan, a student of Anupam Gupta at Carnegie Mellon University.
D. Woodruff completed his MIT Ph.D. thesis "Efficient and Private Distance Approximation in the Communication and Streaming Models" in September, 2007.
Personnel
Short-Term Visitors
- Lisa Fleischer (August 27-31, 2007)
Transitions (in chronological order)
-
Aranyak Mehta completed his postdoctoral assignment and left the department in August, 2007.
- Robi Krauthgamer is on leave as of July, 2007.
- Vitaly Feldman joined the department as Research Staff Member in August, 2007.
- David Woodruff joined the department as Research Staff Member in August, 2007.
- T. S. Jayram became the manager of a new group "Algorithms and Computation" in October 2007.
- Administrative Assistant Desra Halka left the department in November, 2007.
- Alan Nash left the department in November, 2007.
Organization
- Phokion Kolaitis, Senior Manager, CS Principles and Methodologies
- Stella Ayala (Administrative Assistant)
- Ron Fagin, Manager, Foundations of Computer Science
- T. S. Jayram, Manager, Algorithms and Computation
- Miki Ajtai
- Ken Clarkson
- Vitaly Feldman
- Elad Hazan
- T. S. Jayram
- Robi Krauthgamer (on leave)
- Nimrod Megiddo
- Elitza Maneva (postdoctoral scholar)
- David Woodruff
|
