Superconcentrators are graphs that have good connectivity without having too many edges. People like them more when they have fewer edges. We found a construction that makes them a tiny bit smaller than before.

Effectiveness of Structural Restrictions for Hybrid CSPs

Published in ISAAC 2015

A strange paper in retrospect. Roughly speaking, it says on which classes of graphs (relational structures) one should not expect combinatorial optimization problems to become computationally easier.

The Complexity of General-Valued CSPs

Published in FOCS 2015, SIAM Journal on Computing 2016

Somewhat heavy theory. A strong result that concludes complexity classification of a large class of discrete optimization problems.

Total variation on a tree

Published in SIAM Journal on Imaging Sciences 2016

Classical approach to image restoration reduces to efficiently solving combinatorial problems on tree structures. We solved them very efficiently.

On the Memory-Hardness of Data-Independent Password-Hashing Functions

Published in ASIACCS 2018

Side project in cryptography. Some proposed password hashing functions are not as safe as it seems. The attacks are related to graph pebbling, cool stuff!

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

Published in SODA 2017, journal version in ACM Transactions on Algorithms, 2018

Matching on general graphs can be generalized in terms of matroids. This has connections to a planar version of constraint satisfaction problems. We developed a nontrivial generalization of the Blossom algorithm that solves a large class of such problems.

Efficient Optimization for Rank-based Loss Functions

Published in CVPR 2018 (oral), HM best paper award

Direct optimization of rank-based metrics can be done via structured SVM framework. But then there is a nasty algorithmical subproblem to deal with. We dealt with it in optimal runtime.

L4: Practical loss-based stepsize adaptation for deep learning

Published in NIPS 2018

Is Adam really the best we can do? An simple enough update rule can dramatically outperform Adam on some datasets. The optimizer turned out not to be very robust but it had its moments such as actually driving the training loss on MNIST to 0.0 in 20 epochs.

Variational Autoencoders Pursue PCA Directions (by Accident)

Published in CVPR 2019

Why variational autoencoders disentangle? Turns out it is due to innocent looking choice of diagonal posterior. Theoretical paper about an accidental connection between VAEs and (nonlinear) principle components (PCA).

Differentiation of Blackbox Combinatorial Solvers

Published in ICLR 2020 (spotlight)

Embed blackbox combinatorial solvers into neural networks without any sacrifices! How to turn c++ code for solving e.g. travelling salesman into a differentiable NN building block. Mostly theoretical work with update rule resembling classical SVM-based methods but revamped to make good theoretical sense for deep learning. The start of #blackboxbackprop.

Optimizing Rank-based Metrics with Blackbox Differentiation

Published in CVPR 2020 (oral) nomination for best paper award

#blackboxbackprop allows to differentiate through the ranking function out of the box. This, along with a few other tricks, allows for efficient optimization of rank-based metrics. With a minimal implementation overhead, we obtain competitive results on metric learning benchmarks and on object detection.

Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers

Published in ECCV 2020

Using #blackboxbackprop, we wrap strong graph matching solvers into neural network building blocks. With additional help of a few architectural tricks, we obtain SOTA on deep graph matching benchmarks (e.g. PASCAL VOC).

Sample-efficient Cross-Entropy Method for Real-time Planning

Published in Arxiv 2020

Cross-Entropy method is a powerful optimizer for model-based RL. But it is too slow for real time deployment. We introduce several adjustments and tricks to bridge the “real time” gap. The resulting iCEM is FAAAAST!

Michal Rolínek

Sitemap

Pages

Posts

portfolio

publications

talks

teaching