School of Informatics

Foundations of Computation Publications

2024

A Denotational Approach to Release/Acquire Concurrency

Dvir, Y., Kammar, O. & Lahav, O., 19 Jan 2024, (Accepted/In press) Proceedings from the European Symposium on Programming (ESOP). p. 1-27 27 p. (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Axioms for the category of Hilbert spaces and linear contractions

Heunen, C., Kornell, A. & Van Der Schaaf, N., 10 Jan 2024, (Accepted/In press) In: Bulletin of the london mathematical society. p. 1-17 17 p.

Research output: Contribution to journalArticlepeer-review

Shoggoth: A Formal Foundation for Strategic Rewriting

Qin, X., O’Connor, L., van Glabbeek, R., Höfner, P., Kammar, O. & Steuwer, M., 5 Jan 2024, In: Proceedings of the ACM on Programming Languages. 8, POPL, p. 61-89 29 p., 3.

Research output: Contribution to journalArticlepeer-review

Open Access
File

With a Few Square Roots, Quantum Computing Is as Easy as Pi

Carette, J., Heunen, C., Kaarsgaard, R. & Sabry, A., 5 Jan 2024, In: Proceedings of the ACM on Programming Languages. 8, POPL, p. 546-574 29 p., 19.

Research output: Contribution to journalArticlepeer-review

Open Access
File
2023

mlirSynth: Automatic, Retargetable Program Raising in Multi-Level IR using Program Synthesis

Brauckmann, A., Polgreen, E., Grosser, T. & O'Boyle, M. F. P., 27 Dec 2023, 2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT). IEEE, p. 39-50 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Machine learning and topological data analysis identify unique features of human papillae in 3D scans

Andreeva, R., Sarkar, A. & Sarkar, R., 14 Dec 2023, In: Scientific Reports. 13, 1, p. 1-14 14 p., 21529.

Research output: Contribution to journalArticlepeer-review

Open Access
File

DeltaNN: Assessing the Impact of Computational Environment Parameters on the Performance of Image Recognition Models

Louloudakis, N., Gibson, P., Cano, J. & Rajan, A., 11 Dec 2023, 2023 IEEE International Conference on Software Maintenance and Evolution (ICSME). IEEE, p. 414-424 11 p. (IEEE International Conference on Software Maintenance and Evolution (ICSME)).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis

Parsert, J. & Polgreen, E., 9 Dec 2023, (Accepted/In press) The 38th Annual AAAI Conference on Artificial Intelligence. AAAI Press, p. 1-9 9 p. (Proceedings of the AAAI Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Multi-client distributed blind quantum computation with the Qline architecture

Polacchi, B., Leichtle, D., Limongi, L., Carvacho, G., Milani, G., Spagnolo, N., Sciarrino, F., Kaplan, M. & Kashefi, E., 25 Nov 2023, In: Nature Communications. 14, 1, p. 1-8 8 p., 7743.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Relative Keys: Putting Feature Explanation into Context

An, S. & Cao, Y., 20 Nov 2023, (Accepted/In press) In: Proceedings of the ACM on Management of Data. p. 1-28 28 p.

Research output: Contribution to journalArticlepeer-review

Fault Localization for Buggy Deep Learning Framework Conversions in Image Recognition

Louloudakis, N., Gibson, P., Cano, J. & Rajan, A., 8 Nov 2023, 38th IEEE/ACM International Conference on Automated Software Engineering. IEEE, p. 1795-1799 5 p. (IEEE/ACM International Conference on Automated Software Engineering (ASE)).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

C2TACO: Lifting Tensor Code to TACO

De Souza Magalhães, J. W., Woodruff, J., Polgreen, E. & O'Boyle, M. F. P., 22 Oct 2023, GPCE 2023: Proceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences. ACM, p. 42–56 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Comprehending queries over finite maps

Ricciotti, W., 22 Oct 2023, PPDP'23: Proceedings of the 25th International Symposium on Principles and Practice of Declarative Programming. ACM Association for Computing Machinery, p. 1-12 12 p. 8. (ACM International Conference Proceedings Series).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Message Chains for Distributed System Verification

Mora, F., Desai, A., Polgreen, E. & Seshia, S. A., 16 Oct 2023, In: Proceedings of the ACM on Programming Languages. 7, OOPSLA2, p. 1-27 27 p., 300.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Conditional Cube Key Recovery Attack on Round-Reduced Xoodyak

Vaziri, M. & Velichkov, V., 4 Oct 2023, Applied Cryptography and Network Security Workshops: ACNS 2023 Satellite Workshops, ADSC, AIBlock, AIHWS, AIoTS, CIMSS, Cloud S&P, SCI, SecMT, SiMLA, Kyoto, Japan, June 19–22, 2023, Proceedings. Springer, Vol. 13907. p. 43-62 20 p. (Lecture Notes in Computer Science; vol. 13907).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Counting vertices of integral polytopes defined by facets

Guo, H. & Jerrum, M., 1 Oct 2023, In: Discrete & computational geometry. 70, 3, p. 975-990 16 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Eris: Measuring discord among multidimensional data sources

Abelló, A. & Cheney, J., 20 Sept 2023, (E-pub ahead of print) In: VLDB Journal. p. 1-25 25 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Formal Mechanised Semantics of CHERI C: Capabilities, Provenance, and Undefined Behaviour

Zaliva, V., Memarian, K., De Oliveira Almeida, R., Clarke, J., Davis, B., Richardson, A., Chisnall, D., Campbell, B., Stark, I., Watson, R. N. M. & Sewell, P., 19 Sept 2023, (Accepted/In press) ASPLOS 2024: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, p. 1-16 16 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Towards Building Verifiable CPS using Lingua Franca*

Lin, S., Manerkar, Y. A., Lohstroh, M., Polgreen, E., Yu, S-J., Jerad, C., Lee, E. A. & Seshia, S. A., 9 Sept 2023, In: ACM Transactions on Embedded Computing Systems. 22, 5, p. 1-24 24 p., 155.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games

Mayr, R. & Dantam, M., 28 Aug 2023, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 272. p. 38:1-38:15 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi Permutations and Jive Compression Mode

Bouvier, C., Briaud, P., Chaidos, P., Perrin, L., Salen, R., Velichkov, V. & Willems, D., 9 Aug 2023, Advances in Cryptology – CRYPTO 2023. Springer, Vol. 14083. p. 507-539 (Lecture Notes in Computer Science; vol. 14083).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

MITra: A Framework for Multi-Instance Graph Traversal

Li, J., Zhao, W., Ntarmos, N., Cao, Y. & Buneman, P., 8 Aug 2023, In: Proceedings of the VLDB Endowment. 16, 10, p. 2551-2564 14 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Compact inverse categories

Heunen, C. & Cockett, R., 4 Aug 2023, Samson Abramsky on Logic and Structure in Computer Science and Beyond . Springer, Vol. 25. p. 813-832 (Outstanding Contributions to Logic).

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Metric Space Magnitude and Generalisation in Neural Networks

Andreeva, R., Limbeck, K., Rieck, B. & Sarkar, R., 28 Jul 2023, Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML). TAG-ML, ICML ed. Journal of Machine Learning Research: Workshop and Conference Proceedings, Vol. 221. p. 242-253 11 p. (Proceedings of Machine Learning Research; vol. 221).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Extracting Graphs Properties with Semantic Joins

Cao, Y., Fan, W., Fu, W., Jin, R., Ou, W. & Li, W., 26 Jul 2023, 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, p. 2262-2275 14 p. (International Conference on Data Engineering).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

An open-source digital contact tracing system tailored to haulage

Muwonge, A., Wee, B. A., Mugerwa, I., Nabunya, E., Mpyangu, C. M., Bronsvoort, M., Ssebaggala, E. R., Kiayias, A., Mwaka, E. S. & Joloba, M. L., 19 Jul 2023, (E-pub ahead of print) In: Frontiers in Digital Health. 5, p. 1-14 13 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields  

Feng, W., Guo, H. & Wang, J., 12 Jul 2023, In: Information and Computation. 294, p. 1-34 105066.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Challenges in Explaining Brain Tumor Detection

Legastelois, B., Rafferty, A., Brennan, P., Chockler, H., Rajan, A. & Belle, V., 11 Jul 2023, TAS 2023 - Proceedings of the 1st International Symposium on Trustworthy Autonomous Systems. ACM Association for Computing Machinery, p. 1-8 8 p. 21. (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

The Linked Data Benchmark Council (LDBC): Driving Competition and Collaboration in the Graph Data Management Space

Szárnyas, G., Bebee, B., Birler, A., Deutsch, A., Fletcher, G., Gabb, H. A., Gosnell, D., Green, A., Guo, Z., Hare, K. W., Hidders, J., Iosup, A., Kiryakov, A., Kovatchev, T., Li, X., Libkin, L., Lin, H., Luo, X., Prat-Pérez, A., Püroja, D., & 13 othersQi, S., van Rest, O., Steer, B. A., Szakállas, D., Tong, B., Waudby, J., Wu, M., Yang, B., Yu, W., Zhang, C., Zhang, J., Zhou, Y. & Boncz, P., 5 Jul 2023, (Accepted/In press) Proceedings of the Fifteenth TPC Technology Conference on Performance Evaluation & Benchmarking. 16 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

PG-Schemas: Schemas for Property Graphs

Angles, R., Bonifati, A., Dumbrava, S., Fletcher, G., Green, A., Hidders, J., Li, B., Libkin, L., Marsault, V., Martens, W., Murlak, F., Plantikow, S., Savković, O., Schmidt, M., Sequeda, J., Staworko, S., Tomaszuk, D., Voigt, H., Vrgoc, D., Wu, M., & 1 othersZivkovic, D., 20 Jun 2023, In: Proceedings of the ACM on Management of Data. 1, 2, p. 1-25 198.

Research output: Contribution to journalArticlepeer-review

Open Access
File

GPC: A Pattern Calculus for Property Graphs

Francis, N., Gheerbrant, A., Guagliardo, P., Libkin, L., Marsault, V., Martens, W., Murlak, F., Peterfreund, L., Rogova, A. & Vrgoc, D., 18 Jun 2023, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’23). ACM Association for Computing Machinery, p. 241-250 (PODS '23).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Querying Incomplete Numerical Data: Between Certain and Possible Answers

Console, M., Libkin, L. & Peterfreund, L., 18 Jun 2023, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’23). ACM Association for Computing Machinery, p. 349-358 (PODS '23).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

SQL Nulls and Two-Valued Logic

Libkin, L. & Peterfreund, L., 18 Jun 2023, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’23). ACM Association for Computing Machinery, p. 11-20 (PODS '23).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Universally Composable Simultaneous Broadcast against a Dishonest Majority

Arapinis, M., Zacharias, T., Lamprou, N., Medley, L. & Kocsis, Á., 16 Jun 2023, PODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. New York: ACM, p. 200-210 11 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions

Feng, W., Guo, H., Jerrum, M. & Wang, J., 12 Jun 2023, In: TheoretiCS. 2, p. 1-7 8.

Research output: Contribution to journalArticlepeer-review

Open Access
File

The immunopeptidome from a genomic perspective: Establishing the noncanonical landscape of MHC class I–associated peptides

Bedran, G., Gasser, H-C., Weke, K., Wang, T., Bedran, D., Laird, A., Battail, C., Zanzotto, F. M., Pesquita, C., Axelson, H., Rajan, A., Harrison, D. J., Palkowski, A., Pawlik, M., Parys, M., O'Neill, J. R., Brennan, P. M., Symeonides, S. N., Goodlett, D. R., Litchfield, K., & 4 othersFahraeus, R., Hupp, T. R., Kote, S. & Alfaro, J. A., 1 Jun 2023, In: Cancer Immunology Research. 11, 6, p. 747-762 39 p., 22-0621.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Transaction Scheduling: From Conflicts to Runtime Conflicts

Cao, Y., Fan, W., Ou, W., Xie, R. & Zhao, W., 30 May 2023, In: Proceedings of the ACM on Management of Data. 1, 1, p. 1-26 26.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Meet-in-the-Filter and Dynamic Counting with Applications to Speck

Biryukov, A., Cardoso dos Santos, L., Teh, J. S., Udovenko, A. & Velichkov, V., 29 May 2023, Applied Cryptography and Network Security : 21st International Conference, ACNS 2023, Proceedings. Tibouchi, M. & Wang, X. (eds.). Springer, Vol. 13905. p. 149-177 29 p. (Lecture Notes in Computer Science; vol. 13905).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Quantum Lock: A Provable Quantum Communication Advantage

Chakraborty, K., Doosti, M., Ma, Y., Wadhwa, C., Arapinis, M. & Kashefi, E., 23 May 2023, In: Quantum. 7, 47 p., 1014.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Synthesising programs with non-trivial constants

Abate, A., Barbosa, H., Barrett, C., David, C., Kesseli, P., Kroening, D., Polgreen, E., Reynolds, A. & Tinelli, C., 13 May 2023, In: Journal of Automated Reasoning. 67, 2, p. 1-25 19.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Isla: Integrating full-scale ISA semantics and axiomatic concurrency models (extended version)

Armstrong, A., Campbell, B., Simner, B., Pulte, C. & Sewell, P., 12 May 2023, (E-pub ahead of print) In: Formal Methods in System Design. 30 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File

Explanations for automatic speech recognition

Wu, X., Bell, P. & Rajan, A., 5 May 2023, ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 5 p. (International Conference on Acoustics, Speech, and Signal Processing (ICASSP)).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Improving certified robustness via statistical learning with logical reasoning

Yang, Z., Zhao, Z., Wang, B., Zhang, J., Li, L., Pei, H., Karlas, B., Liu, J., Guo, H., Zhang, C. & Li, B., 1 Apr 2023, Advances in Neural Information Processing Systems 35 (NeurIPS 2022). Curran Associates Inc, Vol. 35. p. 34859-34873 15 p. (Advances in Neural Information Processing Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Tracking and viewing modifications in digital calibration certificates

Galpin, V., Smith, I. & Hippolyte, J-L., 30 Mar 2023, In: Acta IMEKO. 12, 1, p. 1-7

Research output: Contribution to journalArticlepeer-review

Open Access
File

A Researcher’s Digest of GQL

Francis, N., Gheerbrant, A., Guagliardo, P., Libkin, L., Marsault, V., Martens, W., Murlak, F., Peterfreund, L., Rogova, A. & Vrgoc, D., 17 Mar 2023, Proceedings of the 26th International Conference on Database Theory (ICDT 2023). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 255. p. 1:1-1:22 22 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 255).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin’s Post-Quantum Security

Cojocaru, A., Garay, J., Kiayias, A., Song, F. & Wallden, P., 9 Mar 2023, In: Quantum. 7, 944, p. 1-32

Research output: Contribution to journalArticlepeer-review

Open Access
File

Duoidally enriched Freyd categories

Heunen, C. & Sigal, J., 8 Mar 2023, Proceedings of the 20th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS 2023). Glück, R., Santocanale, L. & Winter, M. (eds.). Springer, p. 241-257 16 p. (Lecture Notes in Computer Science; vol. 13896, no. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Quantum cryptography beyond quantum key distribution: variants of quantum oblivious transfer

Andersson, E., Stroh, L., Puthoor, I. V., Reichmuth, D., Horova, N., Starek, R., Micuda, M., Dusek, M., Wallden, P., Hemmer, P. R. (ed.) & Migdall, A. L. (ed.), 8 Mar 2023, Quantum Computing, Communication, and Simulation III. Hemmer, P. R. & Migdall, A. L. (eds.). SPIE, Vol. 12446. p. 1-7 (Proceedings of SPIE; vol. 12446).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access
File

Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs

Mayr, R. & Munday, E., 6 Mar 2023, In: Logical Methods in Computer Science. 19, 1, p. 1-43

Research output: Contribution to journalArticlepeer-review

Open Access
File

Variational quantum solutions to the Shortest Vector Problem

Albrecht, M., Prokop, M., Shen, Y. & Wallden, P., 2 Mar 2023, In: Quantum. 7, 933, p. 1-16 16 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File