Vacancies

No vacancies currently.

News

Current events

QuSoft Seminar: Rahul Ilango (MIT)

  • 2021-04-01T13:00:00+02:00
  • 2021-04-01T14:00:00+02:00
April 1 Thursday

Start: 2021-04-01 13:00:00+02:00 End: 2021-04-01 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 (worst-case) 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 average-case 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 NP-hardness for an oracle-version, a multi-output version, and a constant-depth 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 depth-d and depth-(d+1) formula complexity.


Please contact Jop Briet or Subhasree Patro if you like to join.

N&O Seminar: Willem Feijen (CWI)

  • 2021-04-01T11:00:00+02:00
  • 2021-04-01T12:00:00+02:00
April 1 Thursday

Start: 2021-04-01 11:00:00+02:00 End: 2021-04-01 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 Speed-up 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 bi-weekly seminar: The Dutch Seminar on Data Systems Design (DSDSD)

  • 2021-03-26T16:15:00+01:00
  • 2021-03-26T17:45:00+01:00
March 26 Friday

Start: 2021-03-26 16:15:00+01:00 End: 2021-03-26 17:45:00+01:00

CWI has initiated a new national bi-weekly seminar called the Dutch Seminar on Data Systsems Design (DSDSD).

DSDSD is co-organized with TUE, TU Delft, and Uva and brings together researchers in data systems. The format is a 90-minute session with two talks, on Friday late afternoon; so DSDSD marks the start of weekend, but is time-wise 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 60-70 attendees so far. In the following weeks there will be talks also by TUE and TU Delft.

QuSoft Seminar: Ryan Mann (University of Bristol)

  • 2021-03-26T11:00:00+01:00
  • 2021-03-26T12:00:00+01:00
March 26 Friday

Start: 2021-03-26 11:00:00+01:00 End: 2021-03-26 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 deletion-contraction 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)

  • 2021-03-25T16:00:00+01:00
  • 2021-03-25T17:00:00+01:00
March 25 Thursday

Start: 2021-03-25 16:00:00+01:00 End: 2021-03-25 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 envy-minimizing 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 two-fold. 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 slot-MILP. 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 local-search  algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.

Michelle Sweering: Breaking k-Trusses. Abstract: This talk is about breaking communities in networks, specifically k-trusses.
A subgraph H of G is a k-truss if each edge of H is contained in at least k-2 triangles in H.
We discuss how to break k-trusses by deleting as few edges as possible.
Since the problem of breaking k-trusses is NP-hard and even hard to approximate, we also give various heuristics.



IGAFIT Algorithmic Colloquium (online series): Tim Roughgarden (Columbia University)

  • 2021-03-25T16:00:00+01:00
  • 2021-03-25T17:00:00+01:00
March 25 Thursday

Start: 2021-03-25 16:00:00+01:00 End: 2021-03-25 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 Worst-Case 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. Worst-case 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 best-possible worst-case performance. Strong worst-case guarantees are the holy grail of algorithm design, providing an application-agnostic 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 worst-case analysis” develops alternatives to worst-case 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 igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.

Members

Associated Members

Publications

Current projects with external funding

  • Enterprise software engineering ()

Related partners

  • ING Bank