Piotr Sankowski

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Online Matching with Delays and Stochastic Arrival Times.

[BibT_eX]

[DOI]

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

2022

A tight bound for shortest augmenting paths on trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Improved feature importance computation for tree models based on the Banzhaf value.

[BibT_eX]

[DOI]

Proceedings of the Uncertainty in Artificial Intelligence, 2022

Subquadratic dynamic path reporting in directed graphs against an adaptive adversary.

[BibT_eX]

[DOI]

Anish Mukherjee

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Improving Ads-Profitability Using Traffic-Fingerprints.

[BibT_eX]

[DOI]

Adam Gabriel Dobrakowski

Proceedings of the Data Mining - 20th Australasian Conference, AusDM 2022, Western Sydney, 2022

2021

Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf.

[BibT_eX]

[DOI]

CoRR, 2021

Budget Feasible Mechanisms on Matroids.

[BibT_eX]

[DOI]

Algorithmica, 2021

A Deterministic Parallel APSP Algorithm and its Applications.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Decomposable Submodular Function Minimization via Maximum Flow.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs.

[BibT_eX]

[DOI]

Jakub Pawlewicz

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Round Compression for Parallel Matching Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Walking randomly, massively, and efficiently.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Improved Distance Queries and Cycle Counting by Frobenius Normal Form.

[BibT_eX]

[DOI]

Karol Wegrzycki

Theory Comput. Syst., 2019

(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Min-Cost Flow in Unit-Capacity Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Shortest Augmenting Paths for Online Matchings on Trees.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Optimal Dynamic Strings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

NC Algorithms for Weighted Planar Perfect Matching and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Online Facility Location with Deletions.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Optimal Decremental Connectivity in Planar Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Planar Perfect Matching is in NC.

[BibT_eX]

[DOI]

CoRR, 2017

Approximate nearest neighbors search without false negatives for l2.

[BibT_eX]

[DOI]

Piotr Wygocki

CoRR, 2017

Why Do Cascade Sizes Follow a Power-Law?

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on World Wide Web, 2017

Decremental single-source reachability in planar digraphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}.

[BibT_eX]

[DOI]

Piotr Wygocki

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Contracting a Planar Graph Efficiently.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ(m10/7 log W) Time.

[BibT_eX]

[DOI]

CoRR, 2016

Online Network Design with Outliers.

[BibT_eX]

[DOI]

Algorithmica, 2016

Online Pricing with Impatient Bidders.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Algorithmic Complexity of Power Law Networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

RecSys Challenge 2016: job recommendations based on preselection of offers and gradient boosting.

[BibT_eX]

[DOI]

Proceedings of the 2016 Recommender Systems Challenge, 2016

There is Something Beyond the Twitter Network.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Conference on Hypertext and Social Media, 2016

Network Elicitation in Adversarial Environment.

[BibT_eX]

[DOI]

Marcin Dziubinski

Proceedings of the Decision and Game Theory for Security - 7th International Conference, 2016

Locality-Sensitive Hashing Without False Negatives for l_p.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015

Stochastic Query Covering for Fast Approximate Document Retrieval.

[BibT_eX]

[DOI]

ACM Trans. Inf. Syst., 2015

The ring design game with fair cost allocation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.

[BibT_eX]

[DOI]

Glencora Borradaile

ACM Trans. Algorithms, 2015

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings.

[BibT_eX]

[DOI]

Marek Cygan

J. ACM, 2015

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Online Bipartite Matching in Offline Time (Abstract).

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

Revenue Maximization Envy-Free Pricing for Homogeneous Resources.

[BibT_eX]

[DOI]

Gianpiero Monaco

Riccardo Colini-Baldeschi

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014

Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks.

[BibT_eX]

[DOI]

CoRR, 2014

Revenue Maximizing Envy-Free Fixed-Price Auctions with Budgets.

[BibT_eX]

[DOI]

Stefano Leonardi

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Implementation of the Iterative Relaxation Algorithm for the Minimum Bounded-Degree Spanning Tree Problem.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Efficiency of Truthful and Symmetric Mechanisms in One-Sided Matching.

[BibT_eX]

[DOI]

Marek Adamczyk

Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Online Bipartite Matching in Offline Time.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Spreading rumours without the network.

[BibT_eX]

[DOI]

Proceedings of the second ACM conference on Online social networks, 2014

2013

Set Covering with Our Eyes Closed.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Dynamic Steiner Tree in Planar Graphs.

[BibT_eX]

[DOI]

CoRR, 2013

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Reachability in graph timelines.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Catch them if you can: how to serve impatient users.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The Ring Design Game with Fair Cost Allocation - [Extended Abstract].

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Revenue maximizing envy-free multi-unit auctions with budgets.

[BibT_eX]

[DOI]

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Single Source - All Sinks Max Flows in Planar Digraphs.

[BibT_eX]

[DOI]

Yahav Nussbaum

Gudmund Skovbjerg Frandsen

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Dynamic normal forms and dynamic characteristic polynomial.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

[BibT_eX]

[DOI]

CoRR, 2011

Stochastic query covering.

[BibT_eX]

[DOI]

Proceedings of the Forth International Conference on Web Search and Web Data Mining, 2011

Improved algorithms for min cut and max flow in undirected planar graphs.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Yahav Nussbaum

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Single valued combinatorial auctions with budgets.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Approximation Algorithms for Union and Intersection Covering Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs

[BibT_eX]

[DOI]

Giuseppe F. Italiano

CoRR, 2010

Combinatorial Auctions with Budgets

[BibT_eX]

[DOI]

CoRR, 2010

Fast Dynamic Transitive Closure with Lookahead.

[BibT_eX]

[DOI]

Marcin Mucha

Algorithmica, 2010

Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.

[BibT_eX]

[DOI]

Glencora Borradaile

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

Maximum weight bipartite matching in matrix multiplication time.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

2008

Processor Efficient Parallel Matching.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

Stochastic analyses for online combinatorial optimization problems.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Algebraic Graph Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

2007

Faster dynamic matchings and vertex connectivity.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Network formation games with local coalitions.

[BibT_eX]

[DOI]

Stefano Leonardi

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Dynamic Plane Transitive Closure.

[BibT_eX]

[DOI]

Krzysztof Diks

Proceedings of the Algorithms, 2007

2006

Maximum Matchings in Planar Graphs via Gaussian Elimination.

[BibT_eX]

[DOI]

Marcin Mucha

Algorithmica, 2006

Weighted Bipartite Matching in Matrix Multiplication Time.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Shortest Paths in Matrix Multiplication Time.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

Subquadratic Algorithm for Dynamic Shortest Distances.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

Improving Web Sites by Automatic Source Code Analysis and Modifications.

[BibT_eX]

[DOI]

Krzysztof Ciebiera

Proceedings of the Web Engineering - 4th International Conference, 2004

Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Maximum Matchings via Gaussian Elimination.

[BibT_eX]

[DOI]

Marcin Mucha

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Alternative Algorithms for Counting All Matchings in Graphs.

[BibT_eX]

[DOI]

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Multisampling: A New Approach to Uniform Sampling and Approximate Counting.

[BibT_eX]

[DOI]