2023 Fall
Welcome to the homepage of CSE 645: Seminar in Languages!
General Information
Course description: We will read papers and discuss research ranging from high-level specifications (such as logic, rules, and sets) to algorithms and methods for efficient implementations of programming languages, with a wide range of applications.
Everyone is welcome. If you are enrolled in the class, you are expected to attend a majority of the meetings and present a paper.
Instructors: Annie Liu, CR Ramakrishnan, Michael Kifer, David Warren, Paul Fodor.
Hours: Thursdays, 11:30AM-12:50PM ET on Zoom https://stonybrook.zoom.us/j/94298584108?pwd=OXRLemROdk8xOHY3NXFRV2xjQmhVUT09
Schedule
8/31 Organization and topics discussion
9/7 Annie: Queries and optimizations #1 - Liu, Yanhong A., and Scott D. Stoller. Recursive rules with aggregation: a simple unified semantics. Journal of Logic and Computation (JLC), Dec 2022 (slides)
9/14 Video and discussions: ML #5 - Kautz, Henry (2020-02-11). The Third AI Summer, Henry Kautz. AAAI 2020 Robert S. Engelmore Memorial Award Lecture
9/21 Video and discussions: ML#6 - Rossi, Francesca (2022-07-06). Thinking Fast and Slow in AI. AAAI 2022 Invited Talk
9/28 John: ML #3 - Padalkar, Parth, Huaduo Wang, and Gopal Gupta. "NeSyFOLD: Extracting Logic Programs from Convolutional Neural Networks" GDE workshop, 2023 (slides by John)
10/5 Justin: ML #7 - Mao, Jiayuan, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. "The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision." ICLR, 2019. (Also at arXiv:1904.12584) (slides by Justin)
10/12 Video and discussions: ML #1 - NeurIPS 2022 tutorial: Probabilistic Circuits: Representations, Learning, and Reasoning 12/5/22 (video slides) Also see YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models Chapters 1-3.
10/19 Mohammad: Dist #3 - Mohammad Javad Amiri, Chenyuan Wu, Divyakant Agrawal, Amr El Abbadi, Boon Thau Loo, Mohammad Sadoghi. The Bedrock of Byzantine Fault Tolerance: A Unified Platform for BFT Protocols Analysis, Implementation, and Experimentation. NSDI 2024 (abstract | slides)
10/26 More discussions and video of ML #1, NeurIPS 2022 tutorial: Probabilistic Circuits: Representations, Learning, and Reasoning esp the part on "Advanced Reasoning, how do structure and reasoning interplay for real-world applications" (video slides)
(Was to be Invited talk: Vincent Gramoli. The Redbelly Block Chain (abstract). Canceled due to an unexpected reason; we will schedule again when Vincent visits next time)
11/2 Thejesh: Dist #1 - Alpernas, Kalev, Aurojit Panda, Leonid Ryzhyk, and Mooly Sagiv. "Cloud-scale runtime verification of serverless applications." In Proceedings of the ACM Symposium on Cloud Computing, pp. 92-107. 2021. (slides by Thejesh)
11/9 Maliha: Query #3 - Wang, Yisu Remy, Max Willsey, and Dan Suciu. "Free Join: Unifying Worst-Case Optimal and Traditional Joins." Proceedings of the ACM on Management of Data 1, no. 2 (2023): 1-23 (slides by Maliha)
11/16 Venkata: ML #8 - L.C. Lamb, A.S. d'Avila Garcez, M.Gori, M.O.R. Prates, P.H.C. Avelar, M.Y. Vardi (2020). "Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective." IJCAI 2020. (Also a version at arXiv:2003.00330) (slides by Venkata)
11/23 Happy Thanksgiving!
11/30 Invited talk: Jan Wielemaker; The Rise, Fall and Future of Prolog (abstract, ICLP 23 invited talk slides)
12/7 Sriya: Vis #1 - Wettel, Richard, and Michele Lanza. "Visualizing software systems as cities." In 2007 4th IEEE International Workshop on Visualizing Software for Understanding and Analysis, pp. 92-99. IEEE, 2007. (Most influential paper award 2020).
Wettel, Richard, Michele Lanza, and Romain Robbes. "Software systems as cities: A controlled experiment." In Proceedings of the 33rd International Conference on Software Engineering, pp. 551-560. 2011. (Download, etc)
Topics with references
Queries and optimizations (aggregates, probabilities, etc)
Liu, Yanhong A., and Scott D. Stoller. "Recursive rules with aggregation: a simple unified semantics" Journal of Logic and Computation 32, no. 8 (2022): 1659-1693.
This is on recursive rules with (negation and) aggregation.
Just what do such rules mean? And then how to compute efficiently, and even optimally? Two smallest examples:
-The barber shaves those who don't shave themselves. Does the barber shave himself?
-Tom will attend the seminar if at least 20 people will attend.What if 19 others will attend?
(The former is the well-known Russell's paradox from 120+ years ago. The latter is an example from the paper above.)
Despite many sophisticated semantics disagreeing with each other, there is a simple unified semantics.
Abo Khamis, Mahmoud, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. "Convergence of datalog over (pre-) semirings." In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 105-117. 2022. (Best paper award)
Wang, Yisu Remy, Max Willsey, and Dan Suciu. "Free Join: Unifying Worst-Case Optimal and Traditional Joins." Proceedings of the ACM on Management of Data 1, no. 2 (2023): 1-23
Machine learning and neuro-symbolic AI (ML)
YooJung Choi Antonio Vergari Guy Van den Broeck. Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models Chapters 1-3.
NeurIPS 2022 tutorial: Probabilistic Circuits: Representations, Learning, and Reasoning 12/5/22 (video | slides)
Khattab, Omar, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang, Christopher Potts, and Matei Zaharia. "Demonstrate-Search-Predict: Composing retrieval and language models for knowledge-intensive NLP" arXiv preprint arXiv:2212.14024 (2022). (implementation)
Padalkar, Parth, Huaduo Wang, and Gopal Gupta. "NeSyFOLD: Extracting Logic Programs from Convolutional Neural Networks" 3rd Workshop on Goal-directed Execution of Answer Set Programs (GDE’23), July 10, 2023
Sarker, Md Kamruzzaman; Zhou, Lu; Eberhart, Aaron; Hitzler, Pascal (2021). "Neuro-symbolic artificial intelligence: Current trends". AI Communications. 34 (3): 197–209. doi:10.3233/AIC-210084. S2CID 239199144.
Kautz, Henry (2020-02-11). The Third AI Summer, Henry Kautz, AAAI 2020 Robert S. Engelmore Memorial Award Lecture.
Rossi, Francesca (2022-07-06). "AAAI2022: Thinking Fast and Slow in AI (AAAI 2022 Invited Talk)".
Mao, Jiayuan, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. "The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision." In International Conference on Learning Representations, ICLR 2019. (Also at arXiv:1904.12584)
L.C. Lamb, A.S. d'Avila Garcez, M.Gori, M.O.R. Prates, P.H.C. Avelar, M.Y. Vardi (2020). "Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective." IJCAI 2020. (Also a version at arXiv:2003.00330)
Distributed systems and smart contracts (Dist)
Alpernas, Kalev, Aurojit Panda, Leonid Ryzhyk, and Mooly Sagiv. "Cloud-scale runtime verification of serverless applications." In Proceedings of the ACM Symposium on Cloud Computing, pp. 92-107. 2021.
Nissl, Markus, and Emanuel Sallinger. "Towards bridging traditional and smart contracts with Datalog-based languages" In Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022) Co-located with the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2022), Genova-Nervi, Italy, pp. 68-82. 2022
Mohammad Javad Amiri, Chenyuan Wu, Divyakant Agrawal, Amr El Abbadi, Boon Thau Loo, Mohammad Sadoghi. The Bedrock of Byzantine Fault Tolerance: A Unified Platform for BFT Protocols Analysis, Implementation, and Experimentation. NSDI 2024
Visualization frameworks (Vis)
Wettel, Richard, and Michele Lanza. "Visualizing software systems as cities." In 2007 4th IEEE International Workshop on Visualizing Software for Understanding and Analysis, pp. 92-99. IEEE, 2007. (Most influential paper award 2020)
Wettel, Richard, Michele Lanza, and Romain Robbes. "Software systems as cities: A controlled experiment." In Proceedings of the 33rd International Conference on Software Engineering, pp. 551-560. 2011.