Foundations of Reasoning with Uncertainty via Real-valued Logics, with Ryan Riegel and Alexander Gray. To appear in Proceedings of the National Academy of Sciences, 2024.
A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases , with Phokion Kolaitis, Domenico Lembo, Lucian Popa, and Federico Scafoglier. International Conference on Principles of Knowledge Representation and Reasoning (KR2023).
On the Number of Quantifiers as a Complexity Measure, with Jonathan Lenchner, Nikhil Vyas, and Ryan Williams. Mathematical Foundations of Computer Science (MFCS22), 2022.
Multi-structural Games and Number of Quantifiers, with Jonathan Lenchner, Kenneth Regan, and Nikhil Vyas. Logic in Computer Science (LICS21), 2021.
Ontology-Enriched Query Answering on Relational Databases, with Shqiponja Ahmetaj, Vasilis Efthymiou, Phokion G. Kolaitis, Chuan Lei, Fatma Ozcan, and Lucian Popa. Innovative Applications of Artificial Intelligence (IAAI21), 2021, 15247-15254.
Logical Neural Networks, with Ryan Riegel, Alexander Gray, Francois Luus, Naweed Khan, Ndivhuwo Makondo, Ismail Yunus Akhalwaya, Haifeng Qian, Francisco Barahona, Udit Sharma, Shajith Ikbal, Hima Karanam, Sumit Neelam, Ankita Likhyani, and Santosh Srivastava. CoRR abs/2006.13155 (2020)
Recursive programs for document spanners, with Liat Peterfreund, Balder ten Cate, and Benny Kimelfeld. Proc. 2019 International Conference on Database Theory, 2019, pp. 13:1-13:18.
Expressive power of entity-linking frameworks, with Douglas Burdick, Phokion Kolaitis, Lucian Popa, and Wang-Chiew Tan. J. Comput. J. Computer and System Sciences 100 (2019), pp. 44-69. Preliminary version appeared in Proc. 2017 International Conference on Database Theory, pp. 10:1-10:18.
An algorithmic view of voting, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. Siam J. Discrete Math. 30,4 (2016), pp. 1978-1996.
A declarative framework for linking entities, with Douglas Burdick, Phokion Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 41,3, Article 17 (June 2016), 38 pages. Preliminary version appeared in Proc. 2015 International Conference on Database Theory, pp. 25-43.
Declarative cleaning of inconsistencies in information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. ACM Trans. on Database Systems 41,1, Article 6 (February 2016), 44 pages. Preliminary version appeared in Proc. 2014 ACM Symposium on Principles of Database Systems (PODS '14), pp. 164-175, under the title "Cleaning inconsistencies in information extraction via prioritized repairs."
Optimal score aggregation algorithms. Proc. ACM Symposium on Principles of Database Systems (PODS '16), p. 55.
A relational framework for information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. SIGMOD RECORD, December 2015, pp. 5--16.
Dichotomies in the complexity of preferred repairs, with Benny Kimelfeld and Phokion Kolaitis. Proc. ACM Symposium on Principles of Database Systems (PODS '15), pp. 3-15.
Document spanners: A formal approach to information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. J. ACM 62, 2 (April 2015), Article 12. Preliminary version appeared in Proc. 2013 ACM Symposium on Principles of Database Systems (PODS '13), pp. 37-48, under the title "Spanners: a formal framework for information extraction''.
Solutions and query rewriting in data exchange, with Marcelo Arenas, Pablo Barcelo, and Leonid Libkin. Information and Computation, 2013, pp. 28-61. Preliminary version appeared under the title "`Locally consistent transformations and query answering in data exchange", in Proc. 2004 ACM Symposium on Principles of Database Systems (PODS '04), pp. 229-240.
Local transformations and conjunctive-query equivalence, with Phokion G. Kolaitis. Proc. 2012 ACM Symposium on Principles of Database Systems (PODS '12), pp. 179-190.
A normal form for preventing redundant tuples in relational databases, with Hugh Darwen and C. J. Date. Proc. 2012 International Conference on Database Theory (ICDT '12), pp. 114-126.
Composition with target constraints, with Marcelo Arenas and Alan Nash. Logical Methods in Computer Science 7, 3:13 (2011), pp. 1-38. (Special issue for selected papers from the 2010 International Conference on Database Theory).
Probabilistic data exchange, with Benny Kimelfeld and Phokion G. Kolaitis. J. ACM 58, 4 (July 2011), Article 15. Preliminary version appeared in Proc. 2010 International Conference on Database Theory (ICDT '10).
Rewrite rules for search database systems, with Benny Kimelfeld, Yunyao Li, Sriram Raghavan, and Shivakumar Vaithyanathan. Proc. 2011 ACM Symposium on Principles of Database Systems (PODS '11), pp. 271-282.
Reverse data exchange: coping with nulls, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 36, 2 (May 2011), Article 11. (Invited from the 2009 ACM Symposium on Principles of Database Systems.)
Schema mapping evolution through composition and inversion, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. In Z, Bellahsene, A. Bonifati, and E. Rahm, editors, Schema Matching and Mapping, Springer, 2011, pp. 191-222.
Epistemic privacy, with Alexandre Evfimievski and David Woodruff. J. ACM 58, 1 (December 2010), Article 2. (Special issue for selected papers from the 2008 ACM Symposium on Principles of Database Systems.)
The structure of inverses in schema mappings, with Alan Nash. J. ACM 57, 6, Oct.2010, Article 31.
Understanding queries in a search database system, with Benny Kimelfeld, Yunyao Li, Sriram Raghavan, and Shivakumar Vaithyanathan. Proc. 2010 ACM Symposium on Principles of Database Systems (PODS '10), pp. 273-284.
Clio: Schema mapping creation and data exchange, with Laura M. Haas, Mauricio A. Hernandez, Renee J. Miller, Lucian Popa, and Yannis Velegrakis. In A. T. Borgida, V. K. Chaudhri, P. Giorgini, and E. S. Yu, editors, Conceptual Modeling: Foundations and Applications, Essays in Honor of John Mylopoulos, LNCS 5600, Springer, 2009, pp. 198-236.
Quasi-inverses of schema mappings, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 33, 2 (June 2008), Article 11. (Special issue for selected papers from the 2007 ACM Symposium on Principles of Database Systems.)
Towards a theory of schema-mapping optimization, with Phokion G. Kolaitis, Alan Nash, and Lucian Popa. Proc. 2008 ACM Symposium on Principles of Database Systems (PODS '08), pp. 33-42.
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.)
Comparing partial rankings, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. SIAM J. Discrete Mathematics 20, 3 (2006), pp. 628-648.
Composing schema mappings: Second-order dependencies to the rescue, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 30, 4 (Dec. 2005), pp. 994-1055. (Special issue for selected papers from the 2004 ACM SIGMOD/PODS Conference).
Efficient Implementation of Large-Scale Multi-Structural Databases, with Phokion Kolaitis, Ravi Kumar, Jasmine Novak, D. Sivakumar, and Andrew Tomkins. Proc. 2005 Very Large Data Bases Conference (VLDB '05), pp. 958-969.
Data exchange: Semantics and query answering, with Phokion Kolaitis, Renee J. Miller, and Lucian Popa. Theoretical Computer Science 336 (2005), pp. 89-124. (Special issue for selected papers from the 2003 International Conference on Database Theory).
Multi-structural databases, with R. Guha, Ravi Kumar, Jasmine Novak, D. Sivakumar, and Andrew Tomkins. Proc. 2005 ACM Symposium on Principles of Database Systems (PODS '05), pp. 184-195.
Data exchange: Getting to the core, with Phokion Kolaitis and Lucian Popa. ACM Trans. on Database Systems 30, 1 (Mar. 2005), pp. 90-101. (Special issue for selected papers from the 2003 ACM Symposium on Principles of Database Systems).
Comparing and aggregating rankings with ties, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. Proc. 2004 ACM Symposium on Principles of Database Systems (PODS '04), pp. 47-58.
Searching the workplace web, with Ravi Kumar, Kevin McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, and David P. Williamson. Proc. 2003 International World Web Conference (WWW '03), pp. 366-375.
Efficient similarity search and classification via rank aggregation, with Ravi Kumar and D. Sivakumar. Proc. 2003 ACM SIGMOD Conference (SIGMOD '03), pp. 301-312. Corrigendum (including Alexandr Andoni and Mihai Patrascu): Proc. 2008 ACM SIGMOD Conference (SIGMOD '08), pp. 1375-1376.
Comparing top k lists, with Ravi Kumar and D. Sivakumar. SIAM J. Discrete Mathematics 17, 1 (2003), pp. 134-160. Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA '03), pp. 28-36.
Optimal aggregation algorithms for middleware, with Amnon Lotem and Moni Naor. J. Computer and System Sciences 66 (2003), pp. 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems (PODS '01), pp. 102-113.
Combining fuzzy information: an overview. SIGMOD Record 31,2, June 2002, pp. 109-118.
Schema management, with Periklis Andritsos, Ariel Fuxman, Laura M. Haas, Mauricio A. Hernandez, Ching-Tien Ho, Anastasios Kementsietsidis, Renee J. Miller, Felix Nauman, Lucian Popa, Yannis Velegrakis, Charlotte Vilarem and Ling-Ling Yan, IEEE Data Engineering Bulletin 25, 3, 2002, pp. 33-39.
Translating web data, with Lucian Popa, Yannis Velegrakis, Renee J. Miller, and Mauricio A. Hernandez. Proc. 2002 Very Large Data Bases Conference (VLDB '02), pp. 598-609.
Query strategies for priced information, with Moses Charikar, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai. J. Computer and System Sciences 64, 2002, pp. 785-819 (Special issue for selected papers from the 2000 ACM Symposium on Theory of Computing).
Compactly encoding unstructured inputs with differential compression, with Miklos Ajtai, Randal Burns, Larry Stockmeyer, and Darrell Long. J. ACM 49, 3, 2002, pp. 318-367.
Data-driven understanding and refinement of schema mappings, with Ling Ling Yan, Renee J. Miller, and Laura M. Haas. Proc. 2001 ACM SIGMOD Conference (SIGMOD '01), pp. 485-496.
The Clio project: managing heterogeneity, with Renee J. Miller, Mauricio A. Hernandez, Laura M. Haas, Lingling Yan, C. T. Howard Ho, and Lucian Popa. ACM SIGMOD Record 30, 1 (March 2001), pp. 78-83.
Static index pruning for information retrieval systems, with David Carmel, Doron Cohen, Eitan Farchi, Michael Herscovici, Yoelle S. Maarek, and Aya Soffer. Proc. 24th ACM SIGIR Conference on Research and Development in Information Retrieval, New Orleans (SIGIR '01), pp. 43-50.
Random walks with "back buttons", with Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, and Andrew Tomkins. Annals of Applied Probability 11, 3, 2001, pp. 810-862. Extended abstract appeared in Proc. 2000 ACM Symposium on Theory of Computing, pp. 484-493.
A formula for incorporating weights into scoring rules, with Edward L. Wimmers. Theoretical Computer Science 239, 2000, pp. 309-338 (Special issue for selected papers from the 1997 International Conference on Database Theory). Preliminary version appeared under the title "Incorporating user preferences in multimedia queries", in Proc. 6th International Conference on Database Theory (ICDT '97), Jan. 1997, Springer-Verlag Lecture Notes in Computer Science 1186, ed. F. Afrati and Ph. Kolaitis, Delphi, pp. 247-261.
The closure of monadic NP, with Miklos Ajtai and Larry Stockmeyer. J. Computer and System Sciences 60, June 2000, pp. 660-716 (Special issue for selected papers from the 1998 ACM Symp. on Theory of Computing).
Logic, complexity, and games, Invited paper, Proc. 15th IEEE Symposium on Logic in Computer Science, Santa Barbara, 2000, p. 3.
Ephemeral document clustering for web applications, with Yoelle Maarek, Israel Ben-Shaul, and Dan Pelleg. IBM Research Report RJ 10186, April 2000.
Allowing users to weight search terms, with Yoelle Maarek. RIAO (Recherche d'Informations Assistee par Ordinateur = Computer-Assisted Information Retrieval) 2000, pp. 682-700.
The hierarchical approach to modeling knowledge and common knowledge, with John Geanakoplos, Joseph Y. Halpern, and Moshe Y. Vardi. International Journal of Game Theory 28, 3, 1999, pp. 331-365. Preliminary version appeared as "The expressive power of the hierarchical approach to modeling knowledge and common knowledge", Fourth Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. Y. Moses, Morgan Kaufmann, 1992, pp. 229-244.
Combining fuzzy information from multiple systems. J. Computer and System Sciences 58, 1999, pp. 83-99 (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems.)
Common knowledge revisited, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Annals of Pure and Applied Logic 96, 1999, pp. 89-105. Preliminary version appeared in Sixth Conf. on Theoretical Aspects of Rationality and Knowledge, ed. Y. Shoham, Morgan Kaufmann, 1996, pp. 283-298. Reprinted in Knowledge Contributors (V.F. Henricks, K.F. Jorgensen, and S.A. Pedersen, eds.), Kluwer, 2003, pp. 87-104.
Relaxing the triangle inequality in pattern matching, with Larry Stockmeyer. International Journal of Computer Vision 30, 3, 1998, pp. 219-231.
Fuzzy queries in multimedia database systems. Invited paper, Proc. Seventeenth ACM Symp. on Principles of Database Systems (PODS '98), Seattle, 1998, pp. 1-10.
Spectra with only unary function symbols, with Arnaud Durand and Bernd Loescher. 1997 Annual Conference of the European Association for Computer Science Logic (CSL'97). In Springer-Verlag Lecture Notes in Computer Science 1414, 1998, ed. M. Nielsen and W. Thomas, pp. 189-202.
Knowledge-based programs, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Distributed Computing 10, 4, 1997, pp. 199-225 (Special issue for selected papers from the 1995 ACM Symposium on Principles of Distributed Computing).
Comparing the power of games on graphs. Mathematical Logic Quarterly 43, 4, 1997, pp. 431-455. This is an expanded version of "Comparing the power of monadic NP games", Logic and Computational Complexity, Springer-Verlag Lecture Notes in Computer Science 960, 1995, ed. D. Leivant, pp. 414-425.
On winning strategies in Ehrenfeucht-Fraisse games, with Sanjeev Arora. Theoretical Computer Science 174, 1997, pp. 97-121.
Easier ways to win logical games. Invited paper, Descriptive Complexity and Finite Models, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Volume 31, 1997, ed. N. Immerman and Ph. Kolaitis, pp. 1-32.
The Garlic project, with Mary Tork Roth, Manish Arya, Laura Haas, Michael J. Carey, William Cody, Peter Schwarz, John Thomas, and Edward L. Wimmes. Proc. 1996 ACM SIGMOD Symposium, Monteal, page 557.
Common knowledge: Now you have it, now you don't, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. In Intelligent Systems: A Semiotics Perspective, Proc. 1996 Int'l Multidisciplinary Conf., Vol. I, Oct. 1996, pp. 177-183.
Efficiently extendible mappings for balanced data distribution, with David M. Choy and Larry Stockmeyer. Algorithmica 16, 1996, pp. 215-232.
Comparing information without leaking it, with Moni Naor and Peter Winkler. Comm. ACM 39, 5, May 1996, pp. 77-85.
A nonstandard approach to the logical omniscience problem, with Joseph Y. Halpern and Moshe Y. Vardi. Artificial Intelligence 79, 2, Dec. 1995, pp. 203-240. Preliminary version appeared in Third Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. R. Parikh, Morgan Kaufmann, 1990, pp. 41-55.
On monadic NP vs. monadic co-NP, with Larry Stockmeyer and Moshe Vardi. Information and Computation 120, 1, July 1995, pp. 78-92. Preliminary version appeared in 1993 IEEE Structure in Complexity Theory Conference, pp. 19-30.
Querying multimedia data from multiple repositories by content: the Garlic project, with William F. Cody, Laura M. Haas, Wayne Niblack, Manish Arya, Michael J. Carey, Myron Flickner, Denis S. Lee, Dragutin Petkovic, Peter M. Schwarz, John Thomas, Mary Tork Roth, John H. Williams, and Edward L. Wimmers. IFIP 2.6 3rd Working Conference on Visual Database Systems (VDB-3), 1995.
Towards heterogeneous multimedia information systems: the Garlic approach, with Michael J. Carey, Laura M. Haas, Peter M. Schwarz, Manish Arya, William F. Cody, Myron Flickner, Allen W. Luniewski, Wayne Niblack, Dragutin Petkovic, John Thomas, John H. Williams, and Edward L. Wimmers. RIDE-DOM '95 (5th Int'l Workshop on Research Issues in Data Engineering: Distributed Object Management), 1995, pp. 124-131.
Reasoning about knowledge and probability, with Joseph Y. Halpern. J. ACM 41, 2, 1994, pp. 340-367. Preliminary version appeared in Second Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. M. Y. Vardi, Morgan Kaufmann, 1988, pp. 277-293. Corrigendum: J. ACM 45, 1, Jan. 1998, p. 214.
A quantitative analysis of modal logic. J. Symbolic Logic 59, 1, March 1994, pp. 209-252.
An operational semantics for knowledge bases, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. National Conference on Artificial Intelligence (AAAI-94), 1994, pp. 1142-1147. This is a later version of "Modeling knowledge bases", Proc. IJCAI Workshop on Hybrid Reasoning, 1993.
Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3-31. Preliminary version appeared as invited paper, 3rd International Conference on Database Theory, Dec. 1990, Springer-Verlag Lecture Notes in Computer Science 470, pp. 3-24.
Simple conditions for guaranteeing higher normal forms for relational databases, with C. J. Date. ACM Trans. on Database Systems 17, 3, Sept. 1992, 465-476. Reprinted in "Relational database, writings 1989 - 1991" by C. J. Date with Hugh Darwen, Addison Wesley, 1992. Response to "Remarks on two new theorems of Date and Fagin", with C. J. Date. SIGMOD RECORD, March 1993, pp. 57-58.
What is an inference rule?, with Joseph Y. Halpern and Moshe Y. Vardi. J. Symbolic Logic 57, 3, Sept. 1992, pp. 1018-1045. A preliminary version of this paper appeared in the Proceedings of the Jerusalem Conference on Information Technology, Oct. 1990, pp. 391-401.
Two views of belief: Belief as generalized probability and belief as evidence, with Joseph Y. Halpern. Artificial Intelligence 54, 1992, pp. 275-317. Preliminary version appeared in National Conference on Artificial Intelligence (AAAI-90), Aug. 1990, pp. 112-119.
What can machines know? On the properties of knowledge in distributed systems, with Joseph Y. Halpern and Moshe Y. Vardi. J. ACM 39, 2, 1992, pp. 328-376. Preliminary version appeared under the name "What can machines know? On the epistemic properties of machines" in National Conference on Artificial Intelligence (AAAI-86), 1986, pp. 428-434.
A new approach to updating beliefs, with Joseph Y. Halpern. In Uncertainty in Artificial Intelligence: Volume VI, ed. P. P. Bonissone, M. Henrion, L. N. Kanal and J. Lemmer, Elsevier, 1991, pp. 347-374. Preliminary version appeared in Conference on Uncertainty in AI, 1990, pp. 317-324.
A model-theoretic analysis of knowledge, with Joseph Y. Halpern and Moshe Y. Vardi. J. ACM 91, 2, April 1991, pp. 382-428. Preliminary version appeared in Proc. 1984 IEEE Symposium on Foundations of Computer Science, West Palm Beach, Florida, pp. 268-278.
Uncertainty, belief, and probability, with Joseph Y. Halpern. Computational Intelligence 7, 1991, pp. 160-173. Preliminary version appeared in International Joint Conference on Artificial Intelligence (IJCAI-89), pp. 1161-1167.
A logic for reasoning about probabilities, with Joseph Y. Halpern and Nimrod Megiddo. Information and Computation 87, July/Aug. 1990, pp. 78-128 (Special issue for selected papers from the 1988 IEEE Symposium on Logic in Computer Science Conference).
Reachability is harder for directed than for undirected finite graphs, with Miklos Ajtai. J. Symbolic Logic 55, 1, March 1990, pp. 113-150. Preliminary version appeared in Proc. 1988 IEEE Symposium on Foundations of Computer Science, pp. 358-367.
I'm OK if you're OK: On the notion of trusting communication, with Joseph Y. Halpern, J. of Philosophical Logic 17, 4, Nov. 1988, 329-354. Reprinted in Philosophical Logic and Artificial Intelligence, ed. R. Thomason, Kluwer, 1989, pp. 9-34. Preliminary version appeared in Proc. IEEE Symposium on Logic in Computer Science, June 1987, pp. 280-292.
Modelling knowledge and action in distributed systems, with Joseph Y. Halpern. Distributed Computing 3, 4, 1989, pp. 159-179. Preliminary version appeared under the title "A formal model of knowledge, action, and communication in distributed systems" in ACM Symposium on Principles of Distributed Computing, 1985, pp. 224-236. Abridged version appeared in Proc. Concurrency 88, 1988, ed. F. H. Vogt, pp. 18-32.
Belief, awareness, and limited reasoning, with Joseph Y. Halpern. Artificial Intelligence 34, 1988, pp. 39-76. Preliminary version appeared in International Joint Conference on Artificial Intelligence (IJCAI-85), Aug. 1985, pp. 491-501.
A simple characterization of database dependency implication, with Yoshito Hanatani. Information Processing Letters 22, 6, May 1986, 281-283.
The theory of data dependencies: a survey, with Moshe Y. Vardi. Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1986, vol. 34, pp. 19-72.
Updating logical databases, with Gabriel Kuper, Jeffrey D. Ullman, and Moshe Y. Vardi. Advances in Computing Research, vol. 3, The Theory of Databases, ed. P. Kanellakis and F. P. Preparata, JAI Press, Greenwich, Conn., 1986, pp. 1-18.
Knowledge and implicit knowledge in a distributed environment, with Moshe Y. Vardi. Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. J. Y. Halpern, Morgan Kaufmann, 1986, pp. 187-206.
Bounded depth, polynomial-size circuits for symmetric functions, with Maria M. Klawe, Nicholas J. Pippenger, and Larry J. Stockmeyer. Theoretical Computer Science 36, 2-3, April 1985, pp. 239-250.
An internal semantics for modal logic, with Moshe Y. Vardi. Proc. 1985 ACM Symp. on Theory of Computing, Providence, RI, pp. 305-315.
Decreasing the nesting depth of expressions involving square roots, with Allan Borodin, John Hopcroft, and Martin Tompa. Journal of Symbolic Computation 1, 1985, pp. 169-188.
The theory of data dependencies: an overview, with Moshe Y. Vardi. Invited paper, Proc. 11th International Colloquium on Automata, Languages, and Programming, Antwerp, July 1984. Appeared in Springer-Verlag Lecture Notes in Computer Science 172, 1984, ed. J. Paradaens, pp. 1-22.
Inclusion dependencies and their interaction with functional dependencies, with Marco Casanova and Christos Papadimitriou. J. Computer and System Sciences 28, 1, Feb. 1984, pp. 29-59. Preliminary version appeared in Proc. First ACM Symp. on Principles of Database Systems (PODS '82), Los Angeles, March 1982, pp. 171-176.
On the structure of Armstrong relations for functional dependencies, with Catriel Beeri, Martin Dowd, and Richard Statman. J. ACM 31, 1, Jan. 1984, pp. 30-46.
On the desirability of acyclic database schemes, with Catriel Beeri, David Maier, and Mihalis Yannakakis. J. ACM 30, 3, July 1983, pp. 479-513.
Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3, July 1983, pp. 514-550.
Acyclic database schemes of various degrees: a painless introduction. Invited paper, Proc. CAAP83 8th Colloquium on Trees in Algebra and Programming, Springer-Verlag Lecture Notes in Computer Science 159, 1983, ed. G. Ausiello and M. Protasi, pp. 65-89.
A fair carpool scheduling algorithm, with John H. Williams. IBM J. Research and Development 27, 2, March 1983, pp. 133-139.
On the semantics of updates for databases, with Jeffrey D. Ullman and Moshe Y. Vardi. Proc. Second ACM Symp. on Principles of Database Systems (PODS '83), Atlanta, 1983, pp. 352-365.
Tools for template dependencies, with David Maier, Jeffrey D. Ullman, and Mihalis Yannakakis. SIAM J. Computing 12, 1, Feb. 1983, pp. 36-59.
Armstrong databases for functional and inclusion dependencies, with Moshe Y. Vardi. Information Processing Letters 16, Jan. 1983, pp. 13-19.
Horn clauses and database dependencies. J. ACM 29, 4, Oct. 1982, pp. 952-985. Preliminary version appeared in Proc. 1980 ACM Symposium on the Theory of Computing, pp. 123-134.
A simplified universal relation assumption and its properties, with Alberto Mendelzon and Jeffrey D. Ullman. ACM Trans. on Database Systems 7, 3, Sept. 1982, pp. 343-360.
Armstrong databases. Invited paper, Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, Kanagawa, Japan, May 1982.
Properties of acyclic database schemes, with Catriel Beeri, David Maier, Alberto Mendelzon, Jeffrey D. Ullman, and Mihalis Yannakakis, ACM Symposium on Theory of Computing (STOC '81), 1981, pp. 355-362
A normal form for relational databases that is based on domains and keys. ACM Trans. on Database Systems 6, 3, Sept. 1981, pp. 387-415.
A note on the existence of continuous functionals, with J. Lawrence Carter. Theoretical Computer Science 16, 1981, pp. 231-235.
An equivalence between relational database dependencies and a fragment of propositional logic, with Yehoshua Sagiv, Claude Delobel, and D. Stott Parker, Jr. J. ACM 28, 3, July 1981, pp. 435-453. Corrigendum: J. ACM 34, 4, Oct. 1987, pp. 1016-1018.
Extendible hashing-a fast access method for dynamic files, with Jurg Nievergelt, Nicholas J. Pippenger, and H. Raymond Strong. ACM Trans. on Database Systems 4, 3, Sept. 1979, pp. 315-344.
Normal forms and relational database operators. Proc. 1979 ACM SIGMOD Conference, ed. P. A. Bernstein, pp. 153-160.
Cold-start vs. warm-start miss ratios, with Malcolm C. Easton. Comm. ACM 21, 10, Oct. 1978, pp. 866-871.
On an authorization mechanism. ACM Trans. on Database Systems 3, 3, Sept. 1978, pp. 310-319.
Efficient calculation of expected miss ratios in the independent reference model, with Thomas G. Price. SIAM J. Computing 7, 3, Aug. 1978, pp. 288-297.
Functional dependencies in a relational database and propositional logic. IBM J. Research and Development 21, 6, Nov. 1977, pp. 534-544.
The decomposition versus the synthetic approach to relational database design. Proc. 1977 Very Large Data Bases Conference, Tokyo, pp. 441-446. Reprinted in: Tutorial: Data Base Management in the 1980's, ed. J. A. Larson and H. A. Freeman, IEEE Computer Society, NY, 1981, pp. 269-274.
Multivalued dependencies and a new normal form for relational databases. ACM Trans. on Database Systems 2, 3, Sept. 1977, pp. 262-278.
The number of finite relational structures. Discrete Math. 19, 1, July 1977, pp. 17-21.
A complete axiomatization for functional and multivalued dependencies in database relations, with Catriel Beeri and John H. Howard, Jr. Proc. 1977 ACM SIGMOD Symposium, ed. D. C. P. Smith, Toronto, pp. 47-61.
Asymptotic miss ratios over independent references. J. Computer and System Sciences 14, 2, April 1977, pp. 222-250.
Probabilities on finite models. J. Symbolic Logic 41, 1, March 1976, pp. 50-58. Abstract appeared in Notices Amer. Math. Soc., 1972, A714 (Abstract no. 72T-E90).
A counterintuitive example of computer paging. Comm. ACM 19, 2, Feb. 1976, pp. 96-97. Corrigendum: Comm. ACM 19, 4, April 1976, p. 187.
The independence of miss ratio on page size, with Malcolm C. Easton. J. ACM 23, 1, Jan. 1976, pp. 128-146.
A spectrum hierarchy. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly) 21, 1975, pp. 123-134.
A two-cardinal characterization of double spectra. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly) 21, 1975, pp. 121-122.
Monadic generalized spectra. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly)21, 1975, pp. 89-96.
L(kappa, lambda)-equivalence of ordinals and a compactness result. Amer. Math. Soc. Notices 21, 2, 1974, p. A-322.
Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, 1974, pp. 43-73. Note: The original version of this paper had no abstract. In 2019 I added an abstract to this paper. This abstract discusses not only (what is now known as) "Fagin's Theorem" on the equivalence of NP and existential second-order logic, but also some less widely known results that are in the paper.
Abstract (and acknowledgments) of Ph.D. thesis, Contributions to the model theory of finite structures, Univ. of California, Berkeley, June 1973. The Ph.D. thesis essentially consists of the five papers Generalized first-order spectra and polynomial-time recognizable sets, Probabilities on finite models, Monadic generalized spectra, A two-cardinal characterization of double spectra, and A spectrum hierarchy.
Representation theory for a class of denumerable Markov chains. J. Math. Analysis and Applications 23, 1968, pp. 500-530. (Senior Thesis, Dartmouth College.)
Combining fuzzy information: an overview. SIGMOD Record 31,2, June 2002, pp. 109-118.
Fuzzy queries in multimedia database systems. Invited paper, Proc. Seventeenth ACM Symp. on Principles of Database Systems, Seattle, 1998, pp. 1-10.
Easier ways to win logical games. Invited paper, Descriptive Complexity and Finite Models, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Volume 31, 1997, ed. N. Immerman and Ph. Kolaitis, pp. 1-32.
Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3-31. Preliminary version appeared as invited paper, 3rd International Conference on Database Theory, Dec. 1990, Springer-Verlag Lecture Notes in Computer Science 470, pp. 3-24.
The theory of data dependencies: a survey, with Moshe Y. Vardi. Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1986, vol. 34, pp. 19-72.
The theory of data dependencies: an overview, with Moshe Y. Vardi. Invited paper, Proc. 11th International Colloquium on Automata, Languages, and Programming, Antwerp, July 1984. Appeared in Springer-Verlag Lecture Notes in Computer Science 172, 1984, ed. J. Paradaens, pp. 1-22.
Acyclic database schemes of various degrees: a painless introduction. Invited paper, Proc. CAAP83 8th Colloquium on Trees in Algebra and Programming, Springer-Verlag Lecture Notes in Computer Science 159, 1983, ed. G. Ausiello and M. Protasi, pp. 65-89.
Armstrong databases. Invited paper, Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, Kanagawa, Japan, May 1982.
Comparing information without leaking it, with Moni Naor and Peter Winkler. Comm. ACM 39, 5, May 1996, pp. 77-85.
A fair carpool scheduling algorithm, with John H. Williams. IBM J. Research and Development 27, 2, March 1983, pp. 133-139.
The closure of monadic NP, with Miklos Ajtai and Larry Stockmeyer. J. Computer and System Sciences 60, June 2000, pp. 660-716 (Special issue for selected papers from the 1998 ACM Symp. on Theory of Computing).
Logic, complexity, and games, Invited paper, Proc. 15th IEEE Symposium on Logic in Computer Science, Santa Barbara, 2000, p. 3.
Spectra with only unary function symbols, with Arnaud Durand and Bernd Loescher. 1997 Annual Conference of the European Association for Computer Science Logic (CSL'97). In Springer-Verlag Lecture Notes in Computer Science 1414, 1998, ed. M. Nielsen and W. Thomas, pp. 189-202.
Comparing the power of games on graphs. Mathematical Logic Quarterly 43, 4, 1997, pp. 431-455. This is an expanded version of "Comparing the power of monadic NP games", Logic and Computational Complexity, Springer-Verlag Lecture Notes in Computer Science 960, 1995, ed. D. Leivant, pp. 414-425.
On winning strategies in Ehrenfeucht-Fraisse games, with Sanjeev Arora. Theoretical Computer Science 174, 1997, pp. 97-121.
Easier ways to win logical games. Invited paper, Descriptive Complexity and Finite Models, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Volume 31, 1997, ed. N. Immerman and Ph. Kolaitis, pp. 1-32.
On monadic NP vs. monadic co-NP, with Larry Stockmeyer and Moshe Vardi. Information and Computation 120, 1, July 1995, pp. 78-92. Preliminary version appeared in 1993 IEEE Structure in Complexity Theory Conference, pp. 19-30.
Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3-31. Preliminary version appeared as invited paper, 3rd International Conference on Database Theory, Dec. 1990, Springer-Verlag Lecture Notes in Computer Science 470, pp. 3-24.
Reachability is harder for directed than for undirected finite graphs, with Miklos Ajtai. J. Symbolic Logic 55, 1, March 1990, pp. 113-150. Preliminary version appeared in Proc. 1988 IEEE Symposium on Foundations of Computer Science, pp. 358-367.
The number of finite relational structures. Discrete Math. 19, 1, July 1977, pp. 17-21.
Probabilities on finite models. J. Symbolic Logic 41, 1, March 1976, pp. 50-58. Abstract appeared in Notices Amer. Math. Soc., 1972, A714 (Abstract no. 72T-E90).
A spectrum hierarchy. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly) 21, 1975, pp. 123-134.
A two-cardinal characterization of double spectra. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly) 21, 1975, pp. 121-122.
Monadic generalized spectra. Zeitschr. f. math. Logik und Grundlagen d. Math. (now Mathematical Logic Quarterly)21, 1975, pp. 89-96.
Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, 1974, pp. 43-73. Note: The original version of this paper had no abstract. In 2019 I added an abstract to this paper. This abstract discusses not only (what is now known as) "Fagin's Theorem" on the equivalence of NP and existential second-order logic, but also some less widely known results that are in the paper.
Abstract (and acknowledgments) of Ph.D. thesis, Contributions to the model theory of finite structures, Univ. of California, Berkeley, June 1973. The Ph.D. thesis essentially consists of the five papers Generalized first-order spectra and polynomial-time recognizable sets, Probabilities on finite models, Monadic generalized spectra, A two-cardinal characterization of double spectra, and A spectrum hierarchy.
The hierarchical approach to modeling knowledge and common knowledge, with John Geanakoplos, Joseph Y. Halpern, and Moshe Y. Vardi. International Journal of Game Theory 28, 3, 1999, pp. 331-365. Preliminary version appeared as "The expressive power of the hierarchical approach to modeling knowledge and common knowledge", Fourth Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. Y. Moses, Morgan Kaufmann, 1992, pp. 229-244.
Common knowledge revisited, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Annals of Pure and Applied Logic 96, 1999, pp. 89-105. Preliminary version appeared in Sixth Conf. on Theoretical Aspects of Rationality and Knowledge, ed. Y. Shoham, Morgan Kaufmann, 1996, pp. 283-298. Reprinted in Knowledge Contributors (V.F. Henricks, K.F. Jorgensen, and S.A. Pedersen, eds.), Kluwer, 2003, pp. 87-104.
Knowledge-based programs, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Distributed Computing 10, 4, 1997, pp. 199-225 (Special issue for selected papers from the 1995 ACM Symposium on Principles of Distributed Computing).
Common knowledge: Now you have it, now you don't, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. In Intelligent Systems: A Semiotics Perspective, Proc. 1996 Int'l Multidisciplinary Conf., Vol. I, Oct. 1996, pp. 177-183.
A nonstandard approach to the logical omniscience problem, with Joseph Y. Halpern and Moshe Y. Vardi. Artificial Intelligence 79, 2, Dec. 1995, pp. 203-240. Preliminary version appeared in Third Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. R. Parikh, Morgan Kaufmann, 1990, pp. 41-55.
Reasoning about knowledge and probability, with Joseph Y. Halpern. J. ACM 41, 2, 1994, pp. 340-367. Preliminary version appeared in Second Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. M. Y. Vardi, Morgan Kaufmann, 1988, pp. 277-293. Corrigendum: J. ACM 45, 1, Jan. 1998, p. 214.
A quantitative analysis of modal logic. J. Symbolic Logic 59, 1, March 1994, pp. 209-252.
An operational semantics for knowledge bases, with Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. National Conference on Artificial Intelligence (AAAI-94), 1994, pp. 1142-1147. This is a later version of "Modeling knowledge bases", Proc. IJCAI Workshop on Hybrid Reasoning, 1993.
Two views of belief: Belief as generalized probability and belief as evidence, with Joseph Y. Halpern. Artificial Intelligence 54, 1992, pp. 275-317. Preliminary version appeared in National Conference on Artificial Intelligence (AAAI-90), Aug. 1990, pp. 112-119.
What can machines know? On the properties of knowledge in distributed systems, with Joseph Y. Halpern and Moshe Y. Vardi. J. ACM 39, 2, 1992, pp. 328-376. Preliminary version appeared under the name "What can machines know? On the epistemic properties of machines" in National Conference on Artificial Intelligence (AAAI-86), 1986, pp. 428-434.
A new approach to updating beliefs, with Joseph Y. Halpern. In Uncertainty in Artificial Intelligence: Volume VI, ed. P. P. Bonissone, M. Henrion, L. N. Kanal and J. Lemmer, Elsevier, 1991, pp. 347-374. Preliminary version appeared in Conference on Uncertainty in AI, 1990, pp. 317-324.
A model-theoretic analysis of knowledge, with Joseph Y. Halpern and Moshe Y. Vardi. J. ACM 91, 2, April 1991, pp. 382-428. Preliminary version appeared in Proc. 1984 IEEE Symposium on Foundations of Computer Science, West Palm Beach, Florida, pp. 268-278.
Uncertainty, belief, and probability, with Joseph Y. Halpern. Computational Intelligence 7, 1991, pp. 160-173. Preliminary version appeared in International Joint Conference on Artificial Intelligence (IJCAI-89), pp. 1161-1167.
I'm OK if you're OK: On the notion of trusting communication, with Joseph Y. Halpern, J. of Philosophical Logic 17, 4, Nov. 1988, 329-354. Reprinted in Philosophical Logic and Artificial Intelligence, ed. R. Thomason, Kluwer, 1989, pp. 9-34. Preliminary version appeared in Proc. IEEE Symposium on Logic in Computer Science, June 1987, pp. 280-292.
Modelling knowledge and action in distributed systems, with Joseph Y. Halpern. Distributed Computing 3, 4, 1989, pp. 159-179. Preliminary version appeared under the title "A formal model of knowledge, action, and communication in distributed systems" in ACM Symposium on Principles of Distributed Computing, 1985, pp. 224-236. Abridged version appeared in Proc. Concurrency 88, 1988, ed. F. H. Vogt, pp. 18-32.
Belief, awareness, and limited reasoning, with Joseph Y. Halpern. Artificial Intelligence 34, 1988, pp. 39-76. Preliminary version appeared in International Joint Conference on Artificial Intelligence (IJCAI-85), Aug. 1985, pp. 491-501.
Knowledge and implicit knowledge in a distributed environment, with Moshe Y. Vardi. Conf. on Theoretical Aspects of Reasoning about Knowledge, ed. J. Y. Halpern, Morgan Kaufmann, 1986, pp. 187-206.
An internal semantics for modal logic, with Moshe Y. Vardi. Proc. 1985 ACM Symp. on Theory of Computing, Providence, RI, pp. 305-315.
Foundations of Reasoning with Uncertainty via Real-valued Logics, with Ryan Riegel and Alexander Gray. To appear in Proceedings of the National Academy of Sciences, 2024.
On the Number of Quantifiers as a Complexity Measure, with Jonathan Lenchner, Nikhil Vyas, and Ryan Williams. Mathematical Foundations of Computer Science (MFCS22), 2022.
Multi-structural Games and Number of Quantifiers, with Jonathan Lenchner, Kenneth Regan, and Nikhil Vyas. Logic in Computer Science (LICS21), 2021.
What is an inference rule?, with Joseph Y. Halpern and Moshe Y. Vardi. J. Symbolic Logic 57, 3, Sept. 1992, pp. 1018-1045. A preliminary version of this paper appeared in the Proceedings of the Jerusalem Conference on Information Technology, Oct. 1990, pp. 391-401.
A logic for reasoning about probabilities, with Joseph Y. Halpern and Nimrod Megiddo. Information and Computation 87, July/Aug. 1990 pp. 78-128. (Special issue for selected papers from the 1988 IEEE Symposium on Logic in Computer Science Conference).
L(kappa, lambda)-equivalence of ordinals and a compactness result. Amer. Math. Soc. Notices 21, 2, 1974, p. A-322.
Solutions and query rewriting in data exchange, with Marcelo Arenas, Pablo Barcelo, and Leonid Libkin. Information and Computation, 2013, pp. 28-61. Preliminary version appeared under the title "`Locally consistent transformations and query answering in data exchange", in Proc. 2004 ACM Symposium on Principles of Database Systems (PODS '04), pp. 229-240.
Local transformations and conjunctive-query equivalence, with Phokion G. Kolaitis. Proc. 2012 ACM Symposium on Principles of Database Systems (PODS '12), pp. 179-190.
Composition with target constraints, with Marcelo Arenas and Alan Nash. Logical Methods in Computer Science 7, 3:13 (2011), pp. 1-38. (Special issue for selected papers from the 2010 International Conference on Database Theory).
Probabilistic data exchange, with Benny Kimelfeld and Phokion G. Kolaitis. J. ACM 58, 4 (July 2011), Article 15. Preliminary version appeared in Proc. 2010 International Conference on Database Theory (ICDT '10).
Reverse data exchange: coping with nulls, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 36, 2 (May 2011), Article 11. (Invited from the 2009 ACM Symposium on Principles of Database Systems.)
Schema mapping evolution through composition and inversion, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. In Z, Bellahsene, A. Bonifati, and E. Rahm, editors, Schema Matching and Mapping, Springer, 2011, pp. 191-222.
The structure of inverses in schema mappings, with Alan Nash. J. ACM 57, 6, Oct.2010, Article 31.
Clio: Schema mapping creation and data exchange, with Laura M. Haas, Mauricio A. Hernandez, Renee J. Miller, Lucian Popa, and Yannis Velegrakis. In A. T. Borgida, V. K. Chaudhri, P. Giorgini, and E. S. Yu, editors, Conceptual Modeling: Foundations and Applications, Essays in Honor of John Mylopoulos, LNCS 5600, Springer, 2009, pp. 198-236.
Quasi-inverses of schema mappings, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 33, 2 (June 2008), Article 11. (Special issue for selected papers from the 2007 ACM Symposium on Principles of Database Systems.)
Towards a theory of schema-mapping optimization, with Phokion G. Kolaitis, Alan Nash, and Lucian Popa. Proc. 2008 ACM Symposium on Principles of Database Systems (PODS '08), pp. 33-42.
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.)
Composing schema mappings: Second-order dependencies to the rescue, with Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 30, 4 (Dec. 2005), pp. 994-1055. (Special issue for selected papers from the 2004 ACM SIGMOD/PODS Conference).
Data exchange: Semantics and query answering, with Phokion Kolaitis, Renee J. Miller, and Lucian Popa. Theoretical Computer Science 336 (2005), pp. 89-124. (Special issue for selected papers from the 2003 International Conference on Database Theory).
Data exchange: Getting to the core, with Phokion Kolaitis and Lucian Popa. ACM Trans. on Database Systems 30, 1 (Mar. 2005), pp. 90-101. (Special issue for selected papers from the 2003 ACM Symposium on Principles of Database Systems).
Schema management, with Periklis Andritsos, Ariel Fuxman, Laura M. Haas, Mauricio A. Hernandez, Ching-Tien Ho, Anastasios Kementsietsidis, Renee J. Miller, Felix Nauman, Lucian Popa, Yannis Velegrakis, Charlotte Vilarem and Ling-Ling Yan, IEEE Data Engineering Bulletin 25, 3, 2002, pp. 33-39.
Translating web data, with Lucian Popa, Yannis Velegrakis, Renee J. Miller, and Mauricio A. Hernandez. Proc. 2002 Very Large Data Bases Conference (VLDB '02), pp. 598-609.
Data-driven understanding and refinement of schema mappings, with Ling Ling Yan, Renee J. Miller, and Laura M. Haas. Proc. 2001 ACM SIGMOD Conference (SIGMOD '01), pp. 485-496.
The Clio project: managing heterogeneity, with Renee J. Miller, Mauricio A. Hernandez, Laura M. Haas, Lingling Yan, C. T. Howard Ho, and Lucian Popa. ACM SIGMOD Record 30, 1 (March 2001), pp. 78-83.
Optimal score aggregation algorithms. Proc. ACM Symposium on Principles of Database Systems (PODS '16), p. 55.
Optimal aggregation algorithms for middleware, with Amnon Lotem and Moni Naor. J. Computer and System Sciences 66 (2003), pp. 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems (PODS '01), pp. 102-113.
Combining fuzzy information: an overview. SIGMOD Record 31,2, June 2002, pp. 109-118.
Combining fuzzy information from multiple systems. J. Computer and System Sciences 58, 1999, pp. 83-99 (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems.)
A formula for incorporating weights into scoring rules, with Edward L. Wimmers. Theoretical Computer Science 239, 2000, pp. 309-338 (Special issue for selected papers from the 1997 International Conference on Database Theory). Preliminary version appeared under the title "Incorporating user preferences in multimedia queries", in Proc. 6th International Conference on Database Theory, Jan. 1997, Springer-Verlag Lecture Notes in Computer Science 1186, ed. F. Afrati and Ph. Kolaitis, Delphi, pp. 247-261.
Fuzzy queries in multimedia database systems. Invited paper, Proc. Seventeenth ACM Symp. on Principles of Database Systems, Seattle, 1998, pp. 1-10.
The Garlic project, with Mary Tork Roth, Manish Arya, Laura Haas, Michael J. Carey, William Cody, Peter Schwarz, John Thomas, and Edward L. Wimmes. Proc. 1996 ACM SIGMOD Symposium, Monteal, page 557.
Querying multimedia data from multiple repositories by content: the Garlic project, with William F. Cody, Laura M. Haas, Wayne Niblack, Manish Arya, Michael J. Carey, Myron Flickner, Denis S. Lee, Dragutin Petkovic, Peter M. Schwarz, John Thomas, Mary Tork Roth, John H. Williams, and Edward L. Wimmers. IFIP 2.6 3rd Working Conference on Visual Database Systems (VDB-3), 1995.
Towards heterogeneous multimedia information systems: the Garlic approach, with Michael J. Carey, Laura M. Haas, Peter M. Schwarz, Manish Arya, William F. Cody, Myron Flickner, Allen W. Luniewski, Wayne Niblack, Dragutin Petkovic, John Thomas, John H. Williams, and Edward L. Wimmers. RIDE-DOM '95 (5th Int'l Workshop on Research Issues in Data Engineering: Distributed Object Management), 1995, pp. 124-131.
A normal form for preventing redundant tuples in relational databases, with Hugh Darwen and C. J. Date. Proc. 2012 International Conference on Database Theory (ICDT '12), pp. 114-126.
Simple conditions for guaranteeing higher normal forms for relational databases, with C. J. Date. ACM Trans. on Database Systems 17, 3, Sept. 1992, 465-476. Reprinted in "Relational database, writings 1989 - 1991" by C. J. Date with Hugh Darwen, Addison Wesley, 1992. Response to "Remarks on two new theorems of Date and Fagin", with C. J. Date. SIGMOD RECORD, March 1993, pp. 57-58.
A simple characterization of database dependency implication, with Yoshito Hanatani. Information Processing Letters 22, 6, May 1986, 281-283.
The theory of data dependencies: a survey, with Moshe Y. Vardi. Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1986, vol. 34, pp. 19-72.
The theory of data dependencies: an overview, with Moshe Y. Vardi. Invited paper, Proc. 11th International Colloquium on Automata, Languages, and Programming, Antwerp, July 1984. Appeared in Springer-Verlag Lecture Notes in Computer Science 172, 1984, ed. J. Paradaens, pp. 1-22.
Inclusion dependencies and their interaction with functional dependencies, with Marco Casanova and Christos Papadimitriou. J. Computer and System Sciences 28, 1, Feb. 1984, pp. 29-59. Preliminary version appeared in Proc. First ACM Symp. on Principles of Database Systems, Los Angeles, March 1982, pp. 171-176.
On the structure of Armstrong relations for functional dependencies, with Catriel Beeri, Martin Dowd, and Richard Statman. J. ACM 31, 1, Jan. 1984, pp. 30-46.
On the desirability of acyclic database schemes, with Catriel Beeri, David Maier, and Mihalis Yannakakis. J. ACM 30, 3, July 1983, pp. 479-513.
Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3, July 1983, pp. 514-550.
Acyclic database schemes of various degrees: a painless introduction. Invited paper, Proc. CAAP83 8th Colloquium on Trees in Algebra and Programming, Springer-Verlag Lecture Notes in Computer Science 159, 1983, ed. G. Ausiello and M. Protasi, pp. 65-89.
Tools for template dependencies, with David Maier, Jeffrey D. Ullman, and Mihalis Yannakakis. SIAM J. Computing 12, 1, Feb. 1983, pp. 36-59.
Armstrong databases for functional and inclusion dependencies, with Moshe Y. Vardi. Information Processing Letters 16, Jan. 1983, pp. 13-19.
Horn clauses and database dependencies. J. ACM 29, 4, Oct. 1982, pp. 952-985. Preliminary version appeared in Proc. 1980 ACM Symposium on the Theory of Computing, pp. 123-134.
A simplified universal relation assumption and its properties, with Alberto Mendelzon and Jeffrey D. Ullman. ACM Trans. on Database Systems 7, 3, Sept. 1982, pp. 343-360.
Armstrong databases. Invited paper, Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, Kanagawa, Japan, May 1982.
Properties of acyclic database schemes, with Catriel Beeri, David Maier, Alberto Mendelzon, Jeffrey D. Ullman, and Mihalis Yannakakis, ACM Symposium on Theory of Computing (STOC '81), 1981, pp. 355-362
A normal form for relational databases that is based on domains and keys. ACM Trans. on Database Systems 6, 3, Sept. 1981, pp. 387-415.
An equivalence between relational database dependencies and a fragment of propositional logic, with Yehoshua Sagiv, Claude Delobel, and D. Stott Parker, Jr. J. ACM 28, 3, July 1981, pp. 435-453. Corrigendum: J. ACM 34, 4, Oct. 1987, pp. 1016-1018.
Normal forms and relational database operators. Proc. 1979 ACM SIGMOD Conference, ed. P. A. Bernstein, pp. 153-160.
Functional dependencies in a relational database and propositional logic. IBM J. Research and Development 21, 6, Nov. 1977, pp. 534-544.
The decomposition versus the synthetic approach to relational database design. Proc. 1977 Very Large Data Bases Conference, Tokyo, pp. 441-446. Reprinted in: Tutorial: Data Base Management in the 1980's, ed. J. A. Larson and H. A. Freeman, IEEE Computer Society, NY, 1981, pp. 269-274.
A complete axiomatization for functional and multivalued dependencies in database relations, with Catriel Beeri and John H. Howard, Jr. Proc. 1977 ACM SIGMOD Symposium, ed. D. C. P. Smith, Toronto, pp. 47-61.
Multivalued dependencies and a new normal form for relational databases. ACM Trans. on Database Systems 2, 3, Sept. 1977, pp. 262-278.
Declarative cleaning of inconsistencies in information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. ACM Trans. on Database Systems 41,1, Article 6 (February 2016), 44 pages. Preliminary version appeared in Proc. 2014 ACM Symposium on Principles of Database Systems (PODS '14), pp. 164-175, under the title "Cleaning inconsistencies in information extraction via prioritized repairs."
Dichotomies in the complexity of preferred repairs, with Benny Kimelfeld and Phokion Kolaitis. Proc. ACM Symposium on Principles of Database Systems (PODS '15), pp. 3-15.
A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases , with Phokion Kolaitis, Domenico Lembo, Lucian Popa, and Federico Scafoglier. International Conference on Principles of Knowledge Representation and Reasoning (KR2023).
Ontology-Enriched Query Answering on Relational Databases, with Shqiponja Ahmetaj, Vasilis Efthymiou, Phokion G. Kolaitis, Chuan Lei, Fatma Ozcan, and Lucian Popa. Innovative Applications of Artificial Intelligence (IAAI21), 2021, 15247-15254.
Rewrite rules for search database systems, with Benny Kimelfeld, Yunyao Li, Sriram Raghavan, and Shivakumar Vaithyanathan. Proc. 2011 ACM Symposium on Principles of Database Systems (PODS '11), pp. 271-282.
Epistemic privacy, with Alexandre Evfimievski and David Woodruff. J. ACM 58, 1 (December 2010), Article 2. (Special issue for selected papers from the 2008 ACM Symposium on Principles of Database Systems.)
Understanding queries in a search database system, with Benny Kimelfeld, Yunyao Li, Sriram Raghavan, and Shivakumar Vaithyanathan. Proc. 2010 ACM Symposium on Principles of Database Systems (PODS '10), pp. 273-284.
Efficient Implementation of Large-Scale Multi-Structural Databases, with Phokion Kolaitis, Ravi Kumar, Jasmine Novak, D. Sivakumar, and Andrew Tomkins. Proc. 2005 Very Large Data Bases Conference (VLDB '05), pp. 958-969.
Multi-structural databases, with R. Guha, Ravi Kumar, Jasmine Novak, D. Sivakumar, and Andrew Tomkins. Proc. 2005 ACM Symposium on Principles of Database Systems (PODS '05), pp. 184-195.
Efficient similarity search and classification via rank aggregation, with Ravi Kumar and D. Sivakumar. Proc. 2003 ACM SIGMOD Conference (SIGMOD '03), pp. 301-312. Corrigendum (including Alexandr Andoni and Mihai Patrascu): Proc. 2008 ACM SIGMOD Conference (SIGMOD '08), pp. 1375-1376.
Query strategies for priced information, with Moses Charikar, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai. J. Computer and System Sciences 64, 2002, pp. 785-819 (Special issue for selected papers from the 2000 ACM Symposium on Theory of Computing).
Updating logical databases, with Gabriel Kuper, Jeffrey D. Ullman, and Moshe Y. Vardi. Advances in Computing Research, vol. 3, The Theory of Databases, ed. P. Kanellakis and F. P. Preparata, JAI Press, Greenwich, Conn., 1986, pp. 1-18.
On the semantics of updates for databases, with Jeffrey D. Ullman and Moshe Y. Vardi. Proc. Second ACM Symp. on Principles of Database Systems, Atlanta, 1983, pp. 352-365.
Extendible hashing-a fast access method for dynamic files, with Jurg Nievergelt, Nicholas J. Pippenger, and H. Raymond Strong. ACM Trans. on Database Systems 4, 3, Sept. 1979, pp. 315-344.
On an authorization mechanism. ACM Trans. on Database Systems 3, 3, Sept. 1978, pp. 310-319.
Optimal score aggregation algorithms. Proc. ACM Symposium on Principles of Database Systems (PODS '16), p. 55.
An algorithmic view of voting, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. Siam J. Discrete Math. 30,4 (2016), pp. 1978-1996.
Comparing partial rankings, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. SIAM J. Discrete Mathematics 20, 3 (2006), pp. 628-648.
Comparing and aggregating rankings with ties, with Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. Proc. 2004 ACM Symposium on Principles of Database Systems (PODS '04), pp. 47-58.
Searching the workplace web, with Ravi Kumar, Kevin McCurley, Jasmine Novak, D. Sivakumar, John A. Tomlin, and David P. Williamson. Proc. 2003 International World Web Conference (WWW '03), pp. 366-375.
Comparing top k lists, with Ravi Kumar and D. Sivakumar. SIAM J. Discrete Mathematics 17, 1 (2003), pp. 134-160. Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA '03), pp. 28-36.
Optimal aggregation algorithms for middleware, with Amnon Lotem and Moni Naor. J. Computer and System Sciences 66 (2003), pp. 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems (PODS '01), pp. 102-113.
Combining fuzzy information: an overview. SIGMOD Record 31,2, June 2002, pp. 109-118.
Static index pruning for information retrieval systems, with David Carmel, Doron Cohen, Eitan Farchi, Michael Herscovici, Yoelle S. Maarek, and Aya Soffer. Proc. 24th ACM SIGIR Conference on Research and Development in Information Retrieval, New Orleans (SIGIR '01), pp. 43-50.
Ephemeral document clustering for web applications, with Yoelle Maarek, Israel Ben-Shaul, and Dan Pelleg. IBM Research Report RJ 10186, April 2000.
A formula for incorporating weights into scoring rules, with Edward L. Wimmers. Theoretical Computer Science 239, 2000, pp. 309-338 (Special issue for selected papers from the 1997 International Conference on Database Theory). Preliminary version appeared under the title "Incorporating user preferences in multimedia queries", in Proc. 6th International Conference on Database Theory, Jan. 1997, Springer-Verlag Lecture Notes in Computer Science 1186, ed. F. Afrati and Ph. Kolaitis, Delphi, pp. 247-261.
Allowing users to weight search terms, with Yoelle Maarek. RIAO (Recherche d'Informations Assistee par Ordinateur = Computer-Assisted Information Retrieval) 2000, pp. 682-700.
Combining fuzzy information from multiple systems. J. Computer and System Sciences 58, 1999, pp. 83-99 (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems.)
Recursive programs for document spanners, with Liat Peterfreund, Balder ten Cate, and Benny Kimelfeld. Proc. 2019 International Conference on Database Theory, 2019, pp. 13:1-13:18.
Expressive power of entity-linking frameworks, with Douglas Burdick, Phokion Kolaitis, Lucian Popa, and Wang-Chiew Tan. J. Comput. J. Computer and System Sciences 100 (2019), pp. 44-69. Preliminary version appeared in Proc. 2017 International Conference on Database Theory, pp. 10:1-10:18.
A declarative framework for linking entities, with Douglas Burdick, Phokion Kolaitis, Lucian Popa, and Wang-Chiew Tan. ACM Trans. on Database Systems 41,3, Article 17 (June 2016), 38 pages. Preliminary version appeared in Proc. 2015 International Conference on Database Theory, pp. 25-43.
Declarative cleaning of inconsistencies in information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. ACM Trans. on Database Systems 41,1, Article 6 (February 2016), 44 pages. Preliminary version appeared in Proc. 2014 ACM Symposium on Principles of Database Systems (PODS '14), pp. 164-175, under the title "Cleaning inconsistencies in information extraction via prioritized repairs."
Spanners: A formal framework for information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. J. ACM 62, 2 (April 2015), Article 12. Preliminary version appeared in Proc. 2013 ACM Symposium on Principles of Database Systems (PODS '13), pp. 37-48.
A relational framework for information extraction, with Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. SIGMOD RECORD, December 2015, pp. 5--16.
Cold-start vs. warm-start miss ratios, with Malcolm C. Easton. Comm. ACM 21, 10, Oct. 1978, pp. 866-871.
Efficient calculation of expected miss ratios in the independent reference model, with Thomas G. Price. SIAM J. Computing 7, 3, Aug. 1978, pp. 288-297.
Asymptotic miss ratios over independent references. J. Computer and System Sciences 14, 2, April 1977, pp. 222-250.
A counterintuitive example of computer paging. Comm. ACM 19, 2, Feb. 1976, pp. 96-97. Corrigendum: Comm. ACM 19, 4, April 1976, p. 187.
The independence of miss ratio on page size, with Malcolm C. Easton. J. ACM 23, 1, Jan. 1976, pp. 128-146.
Probabilistic data exchange, with Benny Kimelfeld and Phokion G. Kolaitis. J. ACM 58, 4 (July 2011), Article 15. Preliminary version appeared in Proc. 2010 International Conference on Database Theory (ICDT '10).
Random walks with "back buttons", with Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, and Andrew Tomkins. Annals of Applied Probability 11, 3, 2001, pp. 810-862. Extended abstract appeared in Proc. 2000 ACM Symposium on Theory of Computing, pp. 484-493.
A logic for reasoning about probabilities, with Joseph Y. Halpern and Nimrod Megiddo. Information and Computation 87, July/Aug. 1990, pp. 78-128 (Special issue for selected papers from the 1988 IEEE Symposium on Logic in Computer Science Conference).
Probabilities on finite models. J. Symbolic Logic 41, 1, March 1976, pp. 50-58. Abstract appeared in Notices Amer. Math. Soc., 1972, A714 (Abstract no. 72T-E90).
Representation theory for a class of denumerable Markov chains. J. Math. Analysis and Applications 23, 1968, pp. 500-530. (Senior Thesis, Dartmouth College.)
Efficient Implementation of Large-Scale Multi-Structural Databases, with Phokion Kolaitis, Ravi Kumar, Jasmine Novak, D. Sivakumar, and Andrew Tomkins. Proc. 2005 Very Large Data Bases Conference (VLDB '05), pp. 958-969.
Compactly encoding unstructured inputs with differential compression, with Miklos Ajtai, Randal Burns, Larry Stockmeyer, and Darrell Long. J. ACM 49, 3, 2002, pp. 318-367.
Static index pruning for information retrieval systems, with David Carmel, Doron Cohen, Eitan Farchi, Michael Herscovici, Yoelle S. Maarek, and Aya Soffer. Proc. 24th ACM SIGIR Conference on Research and Development in Information Retrieval, New Orleans (SIGIR '01), pp. 43-50.
Ephemeral document clustering for web applications, with Yoelle Maarek, Israel Ben-Shaul, and Dan Pelleg. IBM Research Report RJ 10186, April 2000.
Relaxing the triangle inequality in pattern matching, with Larry Stockmeyer. International Journal of Computer Vision 30, 3, 1998, pp. 219-231.
Efficiently extendible mappings for balanced data distribution, with David M. Choy and Larry Stockmeyer. Algorithmica 16, 1996, pp. 215-232.
Bounded depth, polynomial-size circuits for symmetric functions, with Maria M. Klawe, Nicholas J. Pippenger, and Larry J. Stockmeyer. Theoretical Computer Science 36, 2-3, April 1985, pp. 239-250.
Extendible hashing-a fast access method for dynamic files, with Jurg Nievergelt, Nicholas J. Pippenger, and H. Raymond Strong. ACM Trans. on Database Systems 4, 3, Sept. 1979, pp. 315-344.
Logical Neural Networks, with Ryan Riegel, Alexander Gray, Francois Luus, Naweed Khan, Ndivhuwo Makondo, Ismail Yunus Akhalwaya, Haifeng Qian, Francisco Barahona, Udit Sharma, Shajith Ikbal, Hima Karanam, Sumit Neelam, Ankita Likhyani, and Santosh Srivastava. CoRR abs/2006.13155 (2020)
Decreasing the nesting depth of expressions involving square roots, with Allan Borodin, John Hopcroft, and Martin Tompa. Journal of Symbolic Computation 1, 1985, pp. 169-188.
A note on the existence of continuous functionals, with J. Lawrence Carter. Theoretical Computer Science 16, 1981, pp. 231-235.