| 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 |
| Max-min greedy matching | 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 |
| On the probe complexity of local computation algorithms | 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 |
| On the power of two, three and four probes | 2019-05-06 | Paper |
| On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm | 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(N^2)\) 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 |
| Finding hidden cliques in linear time | 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 |
| Complete convergence of message passing algorithms for some satisfiability problems | 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 |
| On estimation algorithms vs approximation algorithms | 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 |
| The submodular welfare problem with demand queries | 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 |
