Vacancies
No vacancies currently.
News
Current events
QuSoft Seminar: Rahul Ilango (MIT)
 20210401T13:00:00+02:00
 20210401T14:00:00+02:00
QuSoft Seminar: Rahul Ilango (MIT)
Start: 20210401 13:00:00+02:00 End: 20210401 14:00:00+02:00
Everyone is welcome to attend the online QuSoft seminar with Rahul Ilango (MIT). Title of his lecture: Towards Hardness for the Minimum Circuit Size Problem.
Abstract:
Understanding the computational complexity of the Minimum Circuit Size Problem (MCSP) has been a longstanding goal in theoretical computer science, dating back to at least the 1950s. Despite this long history of study, relatively little is known unconditionally about the complexity of MCSP. In particular, it is a major open problem to show MCSP is intractable
under standard (worstcase) complexity assumptions. In recent years, this question has gained renewed importance as researchers have discovered connections between MCSP and a growing number of fields, including to cryptography, learning theory, and averagecase complexity. In this talk, I will discuss some of the context related to research on MCSP and overview three recent joint works that prove hardness results for several natural variants of MCSP. This includes NPhardness for an oracleversion, a multioutput version, and a constantdepth formula version. I will discuss the last result in the most detail and highlight an application that establishes the existence of functions with a 2^{\Omega_d(n)} additive gap between their depthd and depth(d+1) formula complexity.
Please contact Jop Briet or Subhasree Patro if you like to join.
N&O Seminar: Willem Feijen (CWI)
 20210401T11:00:00+02:00
 20210401T12:00:00+02:00
N&O Seminar: Willem Feijen (CWI)
Start: 20210401 11:00:00+02:00 End: 20210401 12:00:00+02:00
Everyone is welcome to attend the online N&O seminar with Willem Feijen (CWI). Title of his lecture: Using Machine Learning Predictions to Speedup Dijkstra's Shortest Path Algorithm.
Abstract:
We study the use of machine learning techniques to solve a fundamental shortest path problem, where the goal is to compute a shortest path from a given source node to any of several designated target nodes. Basically, our idea is to combine a machine learning approach with an adapted version of Dijkstra's algorithm: Based on the trace of the algorithm, we use a neural network to predict the shortest path distance after only a few iterations.
Using this prediction, we can prune the search space explored by Dijkstra's algorithm which avoids a significant number of priority queue operations. Crucially, our approach always computes the exact shortest path distances and never uses more queue operations than the standard algorithm. We prove a lower bound on the number of queue operations saved by our new algorithm, which depends on the accuracy of the prediction. Our bound applies to arbitrary graphs as long as the edge weights are drawn at random. Our experimental findings on random instances confirm these bounds and show that the actual savings are oftentimes significantly higher.
Joint work with Guido Schäfer (CWI & UvA).
New national biweekly seminar: The Dutch Seminar on Data Systems Design (DSDSD)
 20210326T16:15:00+01:00
 20210326T17:45:00+01:00
New national biweekly seminar: The Dutch Seminar on Data Systems Design (DSDSD)
Start: 20210326 16:15:00+01:00 End: 20210326 17:45:00+01:00
CWI has initiated a new national biweekly seminar called the Dutch Seminar on Data Systsems Design (DSDSD).
DSDSD is coorganized with TUE, TU Delft, and Uva and brings together researchers in data systems. The format is a 90minute session with two talks, on Friday late afternoon; so DSDSD marks the start of weekend, but is timewise also friendly for US based speakers. In each seminar, there is one invited speaker from abroad and one local speaker. There have been two seminars already, this Friday is the third.
The website is
https://dsdsd.da.cwi.nl
(here people can get on the mailing list, which distributes the zoom links) and DSDSD also tweets at https://twitter.com/dsdsdnl
We have had two succesful seminars so far, the first with Semih Salihoglu (University of Waterloo) and Hannes Muehleisen (CWI) and the second with Andy Pavlo (Carnegie Mellon University) and Peter Boncz. Friday is the third, with Viktor Leis (University of Erlangen) and Sam Ansmink (CWI). In these seminars, we see 6070 attendees so far. In the following weeks there will be talks also by TUE and TU Delft.
QuSoft Seminar: Ryan Mann (University of Bristol)
 20210326T11:00:00+01:00
 20210326T12:00:00+01:00
QuSoft Seminar: Ryan Mann (University of Bristol)
Start: 20210326 11:00:00+01:00 End: 20210326 12:00:00+01:00
Everyone is welcome to attend the online QuSoft lecture of Ryan Mann (University of Bristol) with the title 'Simulating Quantum Computations with Tutte Polynomials'.
Abstract:
We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping
output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphs. The algorithm evaluates the Tutte polynomial recursively using the deletioncontraction property while attempting to exploit structural properties of the graph. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits. Contrary to the paper, this talk will avoid the language of matroids.
Please contact Suhasree Patro or Jop Briet for the zoom link.
Dutch Seminar on Optimization (online series) with Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
 20210325T16:00:00+01:00
 20210325T17:00:00+01:00
Dutch Seminar on Optimization (online series) with Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
Start: 20210325 16:00:00+01:00 End: 20210325 17:00:00+01:00
Everyone is welcome to attend the Dutch Seminar on Optimization (online series) with:
Moritz Buchem: Additive Approximation Schemes for Load Balancing problem. Abstract: We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envyminimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.
Our technical contribution is twofold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slotMILP. While it has a linear number of integral variables, we identify structural properties of (near)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a localsearch algorithm which rounds any given solution to the slotMILP, introducing an additive error on the machine loads of at most εpmax.
Michelle Sweering: Breaking kTrusses. Abstract: This talk is about breaking communities in networks, specifically ktrusses.
A subgraph H of G is a ktruss if each edge of H is contained in at least k2 triangles in H.
We discuss how to break ktrusses by deleting as few edges as possible.
Since the problem of breaking ktrusses is NPhard and even hard to approximate, we also give various heuristics.
IGAFIT Algorithmic Colloquium (online series): Tim Roughgarden (Columbia University)
 20210325T16:00:00+01:00
 20210325T17:00:00+01:00
IGAFIT Algorithmic Colloquium (online series): Tim Roughgarden (Columbia University)
Start: 20210325 16:00:00+01:00 End: 20210325 17:00:00+01:00
IGAFIT Algorithmic Colloquium is a online seminar series organized by IGAFIT. The event aims to provide a forum for research exchange and scientific interaction, to integrate the European algorithmic community, and to keep the community connected during the times of the pandemic. The goal is to present the highlights of algorithmic research and the most exciting works in this area. Nikhil Bansal (CWI, N&O group) is member of the organizing committee.
The upcoming seminar features Tim Roughgarden (Columbia University). Title of his lecture: Beyond WorstCase Analysis.
Abstract: One of the primary goals of the mathematical analysis of algorithms is to provide guidance about which algorithm is the “best” for solving a given computational problem. Worstcase analysis summarizes the performance profile of an algorithm by its worst performance on any input of a given size, implicitly advocating for the algorithm with the bestpossible worstcase performance. Strong worstcase guarantees are the holy grail of algorithm design, providing an applicationagnostic certification of an algorithm’s robustly good performance.
However, for many fundamental problems and performance measures, such guarantees are impossible and a more nuanced analysis approach is called for. Research in “beyond worstcase analysis” develops alternatives to worstcase analysis, with applications ranging from clustering to linear programming to neural network training. This talk will highlight a mix of classic results, recent developments, and open questions in the area.
To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafitcolloquiumrequest@mimuw.edu.pl with subject SUBSCRIBE.
Members
Associated Members
Publications

Vinju, J.J. (2020). Noisy numbers : column I/O magazine. I/O Magazine : ICT Research Platform Nederland, 17(3), 3–3.

van Binsbergen, L.T, Verano Merino, M, Jeanjean, P, van der Storm, T, Combemale, B, & Barais, O. (2020). A principled approach to REPL interpreters. In Onward! 2020  Proceedings of the 2020 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Colocated with SPLASH 2020 (pp. 84–100). doi:10.1145/3426428.3426917

Verano Merino, M, & van der Storm, T. (2020). Blockbased syntax from contextfree grammars. In SLE 2020  Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, Colocated with SPLASH 2020 (pp. 283–295). doi:10.1145/3426425.3426948

van der Storm, T, & Bakker, G. (2020). MATLAB doesn't love me: An essay. In ACM International Conference Proceeding Series (pp. 97–101). doi:10.1145/3397537.3397557

van Rozen, R.A. (2020, February 19). Languages of games and play : automating game design and enabling live programming. IPA dissertation series.

Aarssen, R.T.A, & van der Storm, T. (2020). Highfidelity metaprogramming with separator syntax trees. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (pp. 27–37). doi:10.1145/3372884.3373162

Azadbakht, K, de Boer, F.S, Bezirgiannis, N, & de Vink, E.P. (2019). A formal actorbased model for streaming the future. Science of Computer Programming, 186. doi:10.1016/j.scico.2019.102341

Soethout, T.M, van der Storm, T, & Vinju, J.J. (2019). Static local coordination avoidance for distributed objects. In AGERE 2019  Proceedings of the 9th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, colocated with SPLASH 2019 (pp. 21–30). doi:10.1145/3358499.3361222

Schaefer, I, Reichenbach, C, & van der Storm, T (Eds.). (2019). GPCE 2019: Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences. In I Schaefer, C Reichenbach, & T van der Storm (Eds.), .

Afroozeh, A, & Izmaylova, A. (2019, June 11). Practical general topdown parsers. IPA dissertation series.
Current projects with external funding

Enterprise software engineering ()
Related partners

ING Bank