University of Warsaw

∙ Warsaw , Poland ∙ 0 followers

The program committee of the ACM Symposium on Theory of Computing (STOC) conference, which presents about 100 most important discoveries in a given year in theoretical computer science, awarded the award for the best work of the article “The Reachability Problem for Petri Nets is Not Elementary”, which co-authors are Wojciech Czerwiński and Sławomir Lasota (Institute of Computer Science, MIM UW).

Uncertainty-sensitive Learning and Planning with Ensembles

We propose a reinforcement learning framework for discrete environments ...
12/19/2019 ∙ by Piotr Miłoś, et al. ∙ 21 ∙ share

read it
Helping AI to Play Hearthstone: AAIA'17 Data Mining Challenge

This paper summarizes the AAIA'17 Data Mining Challenge: Helping AI to P...
08/02/2017 ∙ by Andrzej Janusz, et al. ∙ 0 ∙ share

read it
Atari games and Intel processors

The asynchronous nature of the state-of-the-art reinforcement learning a...
05/19/2017 ∙ by Robert Adamski, et al. ∙ 0 ∙ share

read it
Multi-Objective Deep Q-Learning with Subsumption Architecture

In this work we present a method for using Deep Q-Networks (DQNs) in mul...
04/21/2017 ∙ by Tomasz Tajmajer, et al. ∙ 0 ∙ share

read it
Approximation and Parameterized Complexity of Minimax Approval Voting

We present three results on the complexity of Minimax Approval Voting. F...
07/26/2016 ∙ by Marek Cygan, et al. ∙ 0 ∙ share

read it
ENet: A Deep Neural Network Architecture for Real-Time Semantic Segmentation

The ability to perform pixel-wise semantic segmentation in real-time is ...
06/07/2016 ∙ by Adam Paszke, et al. ∙ 0 ∙ share

read it
A Prior Distribution over Directed Acyclic Graphs for Sparse Bayesian Networks

The main contribution of this article is a new prior distribution over d...
04/25/2015 ∙ by Felix L. Rios, et al. ∙ 0 ∙ share

read it
An Analysis of Deep Neural Network Models for Practical Applications

Since the emergence of Deep Neural Networks (DNNs) as a prominent techni...
05/24/2016 ∙ by Alfredo Canziani, et al. ∙ 0 ∙ share

read it
Optimal Tableau Decision Procedures for PDL

We reformulate Pratt's tableau decision procedure of checking satisfiabi...
04/04/2009 ∙ by Linh Anh Nguyen, et al. ∙ 0 ∙ share

read it
The Erdős-Hajnal conjecture for caterpillars and their complements

The celebrated Erdős-Hajnal conjecture states that for every proper here...
10/24/2017 ∙ by Anita Liebenau, et al. ∙ 0 ∙ share

read it
Improved approximate near neighbor search without false negatives for l_2

We present a new algorithm for the c--approximate nearest neighbor searc...
09/28/2017 ∙ by Piotr Wygocki, et al. ∙ 0 ∙ share

read it
Planar Perfect Matching is in NC

In this paper we show that the problem of computing perfect matchings in...
09/22/2017 ∙ by Piotr Sankowski, et al. ∙ 0 ∙ share

read it
When the Optimum is also Blind: a New Perspective on Universal Optimization

Consider the following variant of the set cover problem. We are given a ...
07/06/2017 ∙ by Marek Adamczyk, et al. ∙ 0 ∙ share

read it
A Quantitative Analysis of Multi-Winner Rules

To choose a multi-winner rule, i.e., a voting rule that selects a subset...
01/04/2018 ∙ by Martin Lackner, et al. ∙ 0 ∙ share

read it
Linear Equations with Ordered Data

Following a recently considered generalization of linear equations to un...
02/19/2018 ∙ by Piotr Hofman, et al. ∙ 0 ∙ share

read it
Analysis of Langevin Monte Carlo via convex optimization

In this paper, we provide new insights on the Unadjusted Langevin Algori...
02/26/2018 ∙ by Alain Durmus, et al. ∙ 0 ∙ share

read it
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

The notions of bounded expansion and nowhere denseness not only offer ro...
02/27/2018 ∙ by Wojciech Nadara, et al. ∙ 0 ∙ share

read it
An improved FPT algorithm for Independent Feedback Vertex Set

We study the Independent Feedback Vertex Set problem - a variant of the ...
03/02/2018 ∙ by Shaohua Li, et al. ∙ 0 ∙ share

read it
Fair non-monetary scheduling in federated clouds

In a hybrid cloud, individual cloud service providers (CSPs) often have ...
03/16/2018 ∙ by Milosz Pacholczyk, et al. ∙ 0 ∙ share

read it
Definable decompositions for graphs of bounded linear cliquewidth

We prove that for every positive integer k, there exists an MSO_1-transd...
03/15/2018 ∙ by Mikołaj Bojańczyk, et al. ∙ 0 ∙ share

read it
Collective Schedules: Scheduling Meets Computational Social Choice

When scheduling public works or events in a shared facility one needs to...
03/20/2018 ∙ by Fanny Pascual, et al. ∙ 0 ∙ share

read it
Losing Treewidth by Separating Subsets

We study the problem of deleting the smallest set S of vertices (resp.ed...
04/04/2018 ∙ by Anupam Gupta, et al. ∙ 0 ∙ share

read it
Subquadratic Approximation Scheme for Partition

The subject of this paper is the time complexity of approximating Knapsa...
04/06/2018 ∙ by Marcin Mucha, et al. ∙ 0 ∙ share

read it
Random Order Contention Resolution Schemes

Contention resolution schemes have proven to be an incredibly powerful c...
04/07/2018 ∙ by Marek Adamczyk, et al. ∙ 0 ∙ share

read it
On Abelian Longest Common Factor with and without RLE

We consider the Abelian longest common factor problem in two scenarios: ...
04/18/2018 ∙ by Szymon Grabowski, et al. ∙ 0 ∙ share

read it
Individual Security and Network Design with Malicious Nodes

Networks are beneficial to those being connected but can also be used as...
04/19/2018 ∙ by Tomasz Janus, et al. ∙ 0 ∙ share

read it
Longest Common Factor Made Fully Dynamic

In the longest common factor (LCF) problem, we are given two strings S a...
04/23/2018 ∙ by Amihood Amir, et al. ∙ 0 ∙ share

read it
Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms

We study an expressive model of timed pushdown automata extended with mo...
04/28/2018 ∙ by Lorenzo Clemente, et al. ∙ 0 ∙ share

read it
Analysis of nonsmooth stochastic approximation: the differential inclusion approach

In this paper we address the convergence of stochastic approximation whe...
05/04/2018 ∙ by Szymon Majewski, et al. ∙ 0 ∙ share

read it
Parameterized circuit complexity of model checking first-order logic on sparse structures

We prove that for every class C of graphs with effectively bounded expan...
05/09/2018 ∙ by Michał Pilipczuk, et al. ∙ 0 ∙ share

read it
Decremental SPQR-trees for Planar Graphs

We present a decremental data structure for maintaining the SPQR-tree of...
06/28/2018 ∙ by Jacob Holm, et al. ∙ 0 ∙ share

read it
Online Facility Location with Deletions

In this paper we study three previously unstudied variants of the online...
07/10/2018 ∙ by Marek Cygan, et al. ∙ 0 ∙ share

read it
A collisionless singular Cucker-Smale model with decentralized formation control

In this paper we address the design of decentralized feedback control la...
07/13/2018 ∙ by Young-Pil Choi, et al. ∙ 0 ∙ share

read it
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs

We consider two optimization problems in planar graphs. In Maximum Weigh...
07/19/2018 ∙ by Michał Pilipczuk, et al. ∙ 0 ∙ share

read it
Undecidability of MSO+"ultimately periodic"

We prove that MSO on ω-words becomes undecidable if allowing to quantify...
07/23/2018 ∙ by Mikołaj Bojańczyk, et al. ∙ 0 ∙ share

read it
Connected Components at Scale via Local Contractions

As a fundamental tool in hierarchical graph clustering, computing connec...
07/27/2018 ∙ by Jakub Łącki, et al. ∙ 0 ∙ share

read it
Asymptotics of maximum likelihood estimators based on Markov chain Monte Carlo methods

In many complex statistical models maximum likelihood estimators cannot ...
08/08/2018 ∙ by Błażej Miasojedow, et al. ∙ 0 ∙ share

read it
Finite Query Answering in Expressive Description Logics with Transitive Roles

We study the problem of finite ontology mediated query answering (FOMQA)...
08/09/2018 ∙ by Tomasz Gogacz, et al. ∙ 0 ∙ share

read it
Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms

We investigate the impact of supervised prediction models on the strengt...
08/14/2018 ∙ by Maciej Świechowski, et al. ∙ 0 ∙ share

read it
An infinitary rewriting interpretation of coinductive types

We introduce an infinitary rewriting semantics for strictly positive nes...
08/15/2018 ∙ by Łukasz Czajka, et al. ∙ 0 ∙ share

read it
Kernelization and approximation of distance-r independent sets on nowhere dense graphs

For a positive integer r, a distance-r independent set in an undirected ...
09/15/2018 ∙ by Michał Pilipczuk, et al. ∙ 0 ∙ share

read it
Constant factor FPT approximation for capacitated k-median

Capacitated k-median is one of the few outstanding optimization problems...
09/16/2018 ∙ by Marek Adamczyk, et al. ∙ 0 ∙ share

read it
The Reachability Problem for Petri Nets is Not Elementary (Extended Abstract)

Petri nets, also known as vector addition systems, are a long establishe...
09/19/2018 ∙ by Wojciech Czerwiński, et al. ∙ 0 ∙ share

read it
First-order interpretations of bounded expansion classes

The notion of bounded expansion captures uniform sparsity of graph class...
10/04/2018 ∙ by Jakub Gajarsky, et al. ∙ 0 ∙ share

read it
Randomized contractions meet lean decompositions

The randomized contractions technique, introduced by Chitnis et al. in 2...
10/16/2018 ∙ by Marek Cygan, et al. ∙ 0 ∙ share

read it
Multi-budgeted directed cuts

We study multi-budgeted variants of the classic minimum cut problem and ...
10/16/2018 ∙ by Stefan Kratsch, et al. ∙ 0 ∙ share

read it
Proportionality Degree of Multiwinner Rules

We study multiwinner elections with approval-based preferences. An insta...
10/20/2018 ∙ by Piotr Skowron, et al. ∙ 0 ∙ share

read it
Hanson-Wright inequality in Banach spaces

We discuss two-sided bounds for moments and tails of quadratic forms in ...
11/01/2018 ∙ by Radosław Adamczak, et al. ∙ 0 ∙ share

read it
Entropy versus variance for symmetric log-concave random variables and related problems

We show that the uniform distribution minimises entropy among all symmet...
11/01/2018 ∙ by Mokshay Madiman, et al. ∙ 0 ∙ share

read it
Almost Optimal Distance Oracles for Planar Graphs

We present new tradeoffs between space and query-time for exact distance...
11/05/2018 ∙ by Panagiotis Charalampopoulos, et al. ∙ 0 ∙ share

read it

University of Warsaw

Featured Researchers