| Publication | Date of Publication | Type |
|---|
| How to hide a clique? | 2024-10-07 | Paper |
| On the path partition number of 6‐regular graphs | 2023-10-05 | Paper |
| On best-of-both-worlds fair-share allocations | 2023-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875458 | 2023-02-03 | Paper |
| A tight negative example for MMS fair allocations | 2022-07-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5077148 | 2022-05-18 | Paper |
| Navigating in Trees with Permanently Noisy Advice | 2022-02-16 | Paper |
| Introduction to Semirandom Models | 2022-02-04 | Paper |
| Target set selection for conservative populations | 2021-10-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002725 | 2021-07-28 | Paper |
| Networks on which hot-potato routing does not livelock | 2020-12-03 | Paper |
| Shotgun assembly of random jigsaw puzzles | 2020-10-26 | Paper |
| Tighter Bounds for Online Bipartite Matching | 2020-07-08 | Paper |
| A new approach to fair distribution of welfare | 2020-06-30 | Paper |
| Finding cliques using few probes | 2020-06-19 | Paper |
| On the Profile of Multiplicities of Complete Subgraphs | 2020-04-07 | Paper |
| Approximate Modularity Revisited | 2020-01-28 | Paper |
| A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time | 2019-10-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633843 | 2019-05-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633854 | 2019-05-06 | Paper |
| A fast randomized LOGSPACE algorithm for graph connectivity | 2019-04-29 | Paper |
| On the cost of recomputing: tight bounds on pebbling with faults | 2019-04-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4617612 | 2019-02-06 | Paper |
| The ordered covering problem | 2018-07-26 | Paper |
| Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time | 2018-07-19 | Paper |
| Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time | 2018-07-16 | Paper |
| Oblivious Rounding and the Integrality Gap | 2018-04-19 | Paper |
| Contagious sets in random graphs | 2018-01-04 | Paper |
| Contagious Sets in Expanders | 2017-10-05 | Paper |
| On the effect of randomness on planted 3-coloring models | 2017-09-29 | Paper |
| A greedy approximation algorithm for minimum-gap scheduling | 2017-09-01 | Paper |
| Approximate modularity revisited | 2017-08-17 | Paper |
| Separation between Estimation and Approximation | 2017-05-19 | Paper |
| Why are Images Smooth? | 2017-05-19 | Paper |
| Invitation games and the price of stability | 2017-05-19 | Paper |
| Welfare maximization and the supermodular degree | 2017-05-16 | Paper |
| Optimization with uniform size queries | 2017-05-11 | Paper |
| Chasing Ghosts: Competing with Stateful Policies | 2017-03-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2959905 | 2017-02-10 | Paper |
| Nonmonotonic phenomena in packet routing | 2016-09-29 | Paper |
| Two prover protocols, low error at affordable rates | 2016-09-01 | Paper |
| A minimal model for secure computation (extended abstract) | 2016-09-01 | Paper |
| Finding OR in a noisy broadcast network | 2016-06-16 | Paper |
| On giant components and treewidth in the layers model | 2016-06-10 | Paper |
| Oblivious algorithms for the maximum directed cut problem | 2015-05-26 | Paper |
| Short random walks on graphs | 2015-05-07 | Paper |
| On the integrality ratio of semidefinite relaxations of MAX CUT | 2015-02-27 | Paper |
| Recoverable Values for Independent Sets | 2015-02-20 | Paper |
| On fair division of a homogeneous good | 2015-01-14 | Paper |
| Musical Chairs | 2014-12-22 | Paper |
| On maximizing welfare when utility functions are subadditive | 2014-11-25 | Paper |
| Finding small balanced separators | 2014-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191589 | 2014-10-06 | Paper |
| Approximating the minimum bisection size (extended abstract) | 2014-09-26 | Paper |
| Approximating the domatic number | 2014-09-26 | Paper |
| Santa claus meets hypergraph matchings | 2014-09-09 | Paper |
| Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph | 2014-08-13 | Paper |
| Min-Max Graph Partitioning and Small Set Expansion | 2014-07-30 | Paper |
| Min-max Graph Partitioning and Small Set Expansion | 2014-07-30 | Paper |
| Demand Queries with Preprocessing | 2014-07-01 | Paper |
| Mechanism design with uncertain inputs | 2014-06-05 | Paper |
| Short Tours through Large Linear Forests | 2014-06-02 | Paper |
| On robustly asymmetric graphs | 2014-02-05 | Paper |
| Connectivity of Random High Dimensional Geometric Graphs | 2013-10-04 | Paper |
| Universal Factor Graphs | 2013-08-12 | Paper |
| A Greedy Approximation Algorithm for Minimum-Gap Scheduling | 2013-06-07 | Paper |
| PASS approximation: a framework for analyzing and designing heuristics | 2013-05-13 | Paper |
| Buffer management for colored packets with deadlines | 2012-12-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3165973 | 2012-10-19 | Paper |
| Maximizing Non-monotone Submodular Functions | 2011-11-07 | Paper |
| Oblivious Collaboration | 2011-10-28 | Paper |
| On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas | 2011-10-27 | Paper |
| An O(n log n) Algorithm for a Load Balancing Problem on Paths | 2011-08-12 | Paper |
| Recoverable Values for Independent Sets | 2011-07-06 | Paper |
| On Optimal Strategies for a Hat Game on Graphs | 2011-06-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002778 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002824 | 2011-05-24 | Paper |
| Hardness results for approximating the bandwidth | 2011-01-18 | Paper |
| Balanced coloring of bipartite graphs | 2010-11-24 | Paper |
| Responsive Lotteries | 2010-10-19 | Paper |
| A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium | 2010-10-19 | Paper |
| Improved approximation algorithms for minimum-weight vertex separators | 2010-08-16 | Paper |
| Combination can be hard | 2010-08-16 | Paper |
| On sums of independent random variables with unbounded variance, and estimating the average degree in a graph | 2010-08-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579476 | 2010-08-06 | Paper |
| Relations between average case complexity and approximation complexity | 2010-08-05 | Paper |
| A preemptive algorithm for maximizing disjoint paths on trees | 2010-05-19 | Paper |
| On Maximizing Welfare When Utility Functions Are Subadditive | 2010-03-17 | Paper |
| An improved approximation ratio for the minimum linear arrangement problem | 2010-01-29 | Paper |
| On the hardness of approximating max-satisfy | 2009-12-18 | Paper |
| PASS Approximation | 2009-10-28 | Paper |
| Combination Can Be Hard: Approximability of the Unique Coverage Problem | 2009-08-20 | Paper |
| Approximating the bandwidth of caterpillars | 2009-07-24 | Paper |
| Finding a Maximum Independent Set in a Sparse Random Graph | 2009-05-27 | Paper |
| Improved Approximation Algorithms for Minimum Weight Vertex Separators | 2009-04-30 | Paper |
| On the complexity of finding balanced oneway cuts | 2009-04-28 | Paper |
| Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs | 2009-02-17 | Paper |
| Small Linear Dependencies for Binary Vectors of Low Weight | 2009-02-12 | Paper |
| Santa Claus Meets Hypergraph Matchings | 2008-11-27 | Paper |
| Edge Coloring and Decompositions of Weighted Graphs | 2008-11-25 | Paper |
| A Preemptive Algorithm for Maximizing Disjoint Paths on Trees | 2008-07-15 | Paper |
| Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems | 2007-08-28 | Paper |
| The RPR2 rounding technique for semidefinite programs | 2006-08-14 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| A Polylogarithmic Approximation of the Minimum Bisection | 2006-06-01 | Paper |
| On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph | 2006-06-01 | Paper |
| Improved approximation of the minimum cover time | 2005-09-22 | Paper |
| Spectral techniques applied to sparse random graphs | 2005-09-22 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2005-08-25 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| Approximating Maximum Clique by Removing Subgraphs | 2005-02-28 | Paper |
| Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers | 2005-02-21 | Paper |
| A threshold of ln n for approximating set cover | 2005-01-25 | Paper |
| Approximating min sum set cover | 2004-11-05 | Paper |
| The inapproximability of lattice and coding problems with preprocessing | 2004-10-04 | Paper |
| Error reduction by parallel repetition - a negative result | 2003-08-06 | Paper |
| Deterministic approximation of the cover time | 2003-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4411280 | 2003-07-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4411281 | 2003-07-07 | Paper |
| The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set | 2003-06-19 | Paper |
| On cutting a few vertices from a graph | 2003-06-10 | Paper |
| On the drift of short schedules. | 2003-01-21 | Paper |
| Approximating theDomatic Number | 2003-01-05 | Paper |
| Improved approximation of Max-Cut on graphs of bounded degree | 2002-09-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542585 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542524 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4549232 | 2002-08-27 | Paper |
| A note on approximating Max-Bisection on regular graphs | 2002-07-14 | Paper |
| Approximation algorithms for maximization problems arising in graph partitioning | 2002-07-08 | Paper |
| Heuristics for semirandom graph problems | 2002-07-04 | Paper |
| On the optimality of the random hyperplane rounding technique for MAX CUT | 2002-07-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535020 | 2002-06-12 | Paper |
| A polylogarithmic approximation of the minimum bisection | 2002-04-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228428 | 2002-01-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2753732 | 2001-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2721963 | 2001-07-11 | Paper |
| The dense \(k\)-subgraph problem | 2001-04-17 | Paper |
| On the hardness of computing the permanent of random matrices | 2001-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527018 | 2001-02-28 | Paper |
| Two-Prover Protocols---Low Error at Affordable Rates | 2000-10-18 | Paper |
| Approximating the bandwidth via volume respecting embeddings | 2000-08-27 | Paper |
| On the cost of recomputing: Tight bounds on pebbling with faults | 2000-08-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4952611 | 2000-05-10 | Paper |
| Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions | 1999-10-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228484 | 1999-10-18 | Paper |
| Zero knowledge and the chromatic number | 1999-10-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4259986 | 1999-09-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4318695 | 1999-08-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234094 | 1999-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228521 | 1999-03-01 | Paper |
| Collecting coupons on trees, and the cover time of random walks | 1998-10-19 | Paper |
| Interactive proofs and the hardness of approximating cliques | 1998-01-21 | Paper |
| Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function | 1998-01-05 | Paper |
| A spectrum of time-space trade-offs for undirected \(s-t\) connectivity | 1998-01-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4341735 | 1997-12-15 | Paper |
| A fast randomized LOGSPACE algorithm for graph connectivity | 1997-02-27 | Paper |
| Random Walks on Regular and Irregular Graphs | 1996-12-09 | Paper |
| Short Random Walks on Graphs | 1996-04-24 | Paper |
| A tight lower bound on the cover time for random walks on graphs | 1996-02-20 | Paper |
| Derandomized graph products | 1995-07-16 | Paper |
| A tight upper bound on the cover time for random walks on graphs | 1995-04-19 | Paper |
| Randomized graph products, chromatic numbers, and Lovasz j-function | 1995-01-01 | Paper |
| Computing with Noisy Information | 1994-11-29 | Paper |
| On the complexity of finite random functions | 1993-05-16 | Paper |
| Multi-oracle interactive protocols with constant space verifiers | 1992-09-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3210167 | 1991-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3210166 | 1990-01-01 | Paper |
| Randomized broadcast in networks | 1990-01-01 | Paper |
| Zero-knowledge proofs of identity | 1988-01-01 | Paper |
