| Publication | Date of Publication | Type |
|---|
| Smoothed complexity of SWAP in local graph partitioning | 2024-11-28 | Paper |
| Reducing Tarski to unique Tarski (In the Black-Box model) | 2024-11-19 | Paper |
| Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP | 2024-09-25 | Paper |
| Computational hardness of the Hylland-Zeckhauser scheme | 2024-07-19 | Paper |
| The smoothed complexity of policy iteration for Markov decision processes | 2024-05-08 | Paper |
| Minimum and maximum delay problems in realtime systems | 2024-04-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875655 | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875712 | 2023-02-03 | Paper |
| Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP | 2022-09-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091153 | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091277 | 2022-07-21 | Paper |
| The platform design problem | 2022-07-06 | Paper |
| On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer | 2022-05-31 | Paper |
| Doubly Balanced Connected Graph Partitioning | 2021-05-03 | Paper |
| Smoothed complexity of local max-cut and binary max-CSP | 2021-01-19 | Paper |
| Planar graphs that need four pages | 2020-09-24 | Paper |
| Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations | 2020-04-30 | Paper |
| Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets | 2020-04-02 | Paper |
| Suboptimal cuts: Their enumeration, weight and number | 2019-12-04 | Paper |
| The Complexity of Optimal Multidimensional Pricing | 2019-06-20 | Paper |
| Recursive stochastic games with positive rewards | 2019-06-18 | Paper |
| Multiway cuts in directed and node weighted graphs | 2019-04-29 | Paper |
| The approximation of maximum subgraph problems | 2019-03-29 | Paper |
| Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover | 2019-03-29 | Paper |
| Power Grid State Estimation Following a Joint Cyber and Physical Attack | 2018-12-19 | Paper |
| Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata | 2018-08-02 | Paper |
| Doubly Balanced Connected Graph Partitioning | 2018-07-16 | Paper |
| The complexity of optimal multidimensional pricing for a unit-demand buyer | 2018-07-12 | Paper |
| Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes | 2018-06-14 | Paper |
| The Complexity of Non-Monotone Markets | 2018-05-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4608026 | 2018-03-15 | Paper |
| A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes | 2017-10-06 | Paper |
| Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems | 2016-09-29 | Paper |
| On complexity as bounded rationality (extended abstract) | 2016-09-01 | Paper |
| How Good is the Chord Algorithm? | 2016-07-04 | Paper |
| Recursive Markov Decision Processes and Recursive Stochastic Games | 2016-03-24 | Paper |
| Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations | 2015-11-11 | Paper |
| Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes | 2015-11-04 | Paper |
| Model Checking of Recursive Probabilistic Systems | 2015-09-17 | Paper |
| A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing | 2015-09-03 | Paper |
| On the value of information in distributed decision-making (extended abstract) | 2015-06-19 | Paper |
| Linear programming without the matrix | 2015-05-07 | Paper |
| On the hardness of approximating minimization problems | 2015-05-07 | Paper |
| Approximate max-flow min-(multi)cut theorems and their applications | 2015-05-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2921785 | 2014-10-13 | Paper |
| Equilibria, fixed points, and complexity classes | 2014-10-07 | Paper |
| The complexity of non-monotone markets | 2014-08-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5417682 | 2014-05-22 | Paper |
| Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars | 2014-05-13 | Paper |
| Node-and edge-deletion NP-complete problems | 2014-03-14 | Paper |
| Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations | 2013-08-12 | Paper |
| Stochastic Context-Free Grammars, Regular Languages, and Newton’s Method | 2013-08-07 | Paper |
| Analysis of Boolean Programs | 2013-08-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4910705 | 2013-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3113724 | 2012-01-23 | Paper |
| Market equilibrium under separable, piecewise-linear, concave utilities | 2011-07-14 | Paper |
| An impossibility theorem for price-adjustment mechanisms | 2011-02-12 | Paper |
| On the Complexity of Nash Equilibria and Other Fixed Points | 2011-01-17 | Paper |
| Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems | 2010-09-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579439 | 2010-08-06 | Paper |
| CONCUR 2003 - Concurrency Theory | 2010-03-30 | Paper |
| Computational Aspects of Equilibria | 2009-12-01 | Paper |
| Recursive Concurrent Stochastic Games | 2009-04-29 | Paper |
| Multi-Objective Model Checking of Markov Decision Processes | 2009-04-29 | Paper |
| Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems | 2009-02-17 | Paper |
| Automata, Probability, and Recursion | 2009-02-12 | Paper |
| Analysis of Recursive Probabilistic Models | 2008-09-04 | Paper |
| Recursive Stochastic Games with Positive Rewards | 2008-08-28 | Paper |
| Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games | 2008-03-19 | Paper |
| Recursive Concurrent Stochastic Games | 2007-09-11 | Paper |
| Multi-objective Model Checking of Markov Decision Processes | 2007-09-03 | Paper |
| Adaptive Model Checking | 2007-02-15 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| Efficiently computing succinct trade-off curves | 2006-01-09 | Paper |
| STACS 2005 | 2005-12-02 | Paper |
| Tools and Algorithms for the Construction and Analysis of Systems | 2005-11-10 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| Realizability and verification of MSC graphs | 2005-04-06 | Paper |
| Multiway cuts in node weighted graphs | 2004-10-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4818841 | 2004-09-24 | Paper |
| Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems | 2004-08-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3044311 | 2004-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4472253 | 2004-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4807832 | 2003-12-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4804922 | 2003-05-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4778537 | 2002-11-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542582 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4551151 | 2002-09-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4536434 | 2002-06-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535063 | 2002-06-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234083 | 2002-01-29 | Paper |
| Markov decision processes and regular events | 2000-10-17 | Paper |
| Timing verification by successive approximation | 2000-07-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4942015 | 2000-03-19 | Paper |
| On the complexity of database queries | 1999-11-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252438 | 1999-06-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218940 | 1999-03-30 | Paper |
| The complexity of probabilistic verification | 1998-01-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4365127 | 1997-10-30 | Paper |
| The input/output complexity of transitive closure | 1997-10-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4356435 | 1997-10-01 | Paper |
| Primal-dual approximation algorithms for integral flow and multicut in trees | 1997-05-28 | Paper |
| On limited nondeterminism and the complexity of the V-C dimension | 1997-03-31 | Paper |
| Tie-breaking semantics and structural totality | 1997-03-18 | Paper |
| Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications | 1996-05-13 | Paper |
| On datalog vs polynomial time | 1995-10-25 | Paper |
| On the hardness of approximating minimization problems | 1995-02-20 | Paper |
| On the Approximation of Maximum Satisfiability | 1994-11-23 | Paper |
| Modularity of cycles and paths in graphs | 1994-11-13 | Paper |
| Linear approximation of shortest superstrings | 1994-11-03 | Paper |
| The Complexity of Multiterminal Cuts | 1994-10-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4277623 | 1994-09-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4302455 | 1994-09-13 | Paper |
| Minimum and maximum delay problems in real-time systems | 1993-09-30 | Paper |
| The Traveling Salesman Problem with Distances One and Two | 1993-06-29 | Paper |
| Computing the throughput of a network with dedicated lines | 1993-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4037099 | 1993-05-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4037388 | 1993-05-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4038703 | 1993-05-18 | Paper |
| Optimization, approximation, and complexity classes | 1992-06-28 | Paper |
| Expressing combinatorial optimization problems by linear programs | 1992-06-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3975934 | 1992-06-26 | Paper |
| Shortest paths without a map | 1991-01-01 | Paper |
| High-Probability Parallel Transitive-Closure Algorithms | 1991-01-01 | Paper |
| Simple Local Search Problems that are Hard to Solve | 1991-01-01 | Paper |
| Batch sizing and job sequencing on a single machine | 1990-01-01 | Paper |
| On recognizing integer polyhedra | 1990-01-01 | Paper |
| Towards an Architecture-Independent Analysis of Parallel Algorithms | 1990-01-01 | Paper |
| Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs | 1989-01-01 | Paper |
| Embedding planar graphs in four pages | 1989-01-01 | Paper |
| Deleting completed transactions | 1989-01-01 | Paper |
| Optimal Scheduling of Products with Two Subassemblies on a Single Machine | 1989-01-01 | Paper |
| On generating all maximal independent sets | 1988-01-01 | Paper |
| How easy is local search? | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3793731 | 1988-01-01 | Paper |
| The maximum k-colorable subgraph problem for chordal graphs | 1987-01-01 | Paper |
| The Complexity of Reliable Concurrency Control | 1987-01-01 | Paper |
| A note on succinct representations of graphs | 1986-01-01 | Paper |
| Deadlock-freedom (and safety) of transactions in a distributed database | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3745305 | 1986-01-01 | Paper |
| Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs | 1985-01-01 | Paper |
| On a Class of Totally Unimodular Matrices | 1985-01-01 | Paper |
| A polynomial algorithm for the min-cut linear arrangement of trees | 1985-01-01 | Paper |
| The complexity of facets (and some facets of complexity) | 1984-01-01 | Paper |
| Independent database schemas | 1984-01-01 | Paper |
| Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs | 1984-01-01 | Paper |
| Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum | 1984-01-01 | Paper |
| Serializability by Locking | 1984-01-01 | Paper |
| Scheduling Opposing Forests | 1983-01-01 | Paper |
| Tools for Template Dependencies | 1983-01-01 | Paper |
| On the Desirability of Acyclic Database Schemes | 1983-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3341921 | 1983-01-01 | Paper |
| Bounds on the size and transmission rate of communications protocols | 1982-01-01 | Paper |
| Algebraic dependencies | 1982-01-01 | Paper |
| The Complexity of the Partial Order Dimension Problem | 1982-01-01 | Paper |
| The complexity of restricted spanning tree problems | 1982-01-01 | Paper |
| Freedom from Deadlock of Safe Locking Policies | 1982-01-01 | Paper |
| A Theory of Safe Locking Policies in Database Systems | 1982-01-01 | Paper |
| On minimal Eulerian graphs | 1981-01-01 | Paper |
| The complexity of testing whether a graph is a superconcentrator | 1981-01-01 | Paper |
| Edge-Deletion Problems | 1981-01-01 | Paper |
| Node-Deletion Problems on Bipartite Graphs | 1981-01-01 | Paper |
| On the Complexity of Testing Implications of Functional and Join Dependencies | 1981-01-01 | Paper |
| Computing the Minimum Fill-In is NP-Complete | 1981-01-01 | Paper |
| Testing the universal instance assumption | 1980-01-01 | Paper |
| The node-deletion problem for hereditary properties is NP-complete | 1980-01-01 | Paper |
| Edge Dominating Sets in Graphs | 1980-01-01 | Paper |
| Equivalences Among Relational Expressions with the Union and Difference Operators | 1980-01-01 | Paper |
| Scheduling Interval-Ordered Tasks | 1979-01-01 | Paper |
| The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems | 1979-01-01 | Paper |
| Topological characterization of families of graphs generated by certain types of graph grammars | 1979-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4190141 | 1979-01-01 | Paper |
