| Publication | Date of Publication | Type |
|---|
How to hide a clique?
Theory of Computing Systems | 2024-10-07 | Paper |
On the path partition number of 6‐regular graphs
Journal of Graph Theory | 2023-10-05 | Paper |
On best-of-both-worlds fair-share allocations
Web and Internet Economics | 2023-08-04 | Paper |
scientific article; zbMATH DE number 7650074 (Why is no real title available?)
| 2023-02-03 | Paper |
A tight negative example for MMS fair allocations
| 2022-07-06 | Paper |
Max-min greedy matching
Theory of Computing | 2022-05-18 | Paper |
Navigating in Trees with Permanently Noisy Advice
ACM Transactions on Algorithms | 2022-02-16 | Paper |
Introduction to Semirandom Models
| 2022-02-04 | Paper |
Target set selection for conservative populations
Discrete Applied Mathematics | 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
Distributed Computing | 2020-12-03 | Paper |
Shotgun assembly of random jigsaw puzzles
Random Structures & Algorithms | 2020-10-26 | Paper |
Tighter bounds for online bipartite matching
Bolyai Society Mathematical Studies | 2020-07-08 | Paper |
A new approach to fair distribution of welfare
| 2020-06-30 | Paper |
Finding cliques using few probes
Random Structures & Algorithms | 2020-06-19 | Paper |
On the profile of multiplicities of complete subgraphs
SIAM Journal on Discrete Mathematics | 2020-04-07 | Paper |
Approximate modularity revisited
SIAM Journal on Computing | 2020-01-28 | Paper |
A polynomial time constant approximation for minimizing total weighted flow-time
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 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
Automata, Languages and Programming | 2019-04-29 | Paper |
On the cost of recomputing: tight bounds on pebbling with faults
Automata, Languages and Programming | 2019-04-29 | Paper |
scientific article; zbMATH DE number 7014202 (Why is no real title available?)
| 2019-02-06 | Paper |
The ordered covering problem
Algorithmica | 2018-07-26 | Paper |
Random walks with the minimum degree local rule have \(O(n^2)\) cover time
SIAM Journal on Computing | 2018-07-19 | Paper |
Random walks with the minimum degree local rule have \(O(N^2)\) cover time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Oblivious rounding and the integrality gap
| 2018-04-19 | Paper |
Contagious sets in random graphs
The Annals of Applied Probability | 2018-01-04 | Paper |
Contagious sets in expanders
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
On the effect of randomness on planted 3-coloring models
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Journal of Scheduling | 2017-09-01 | Paper |
Approximate modularity revisited
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Separation between estimation and approximation
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Why are images smooth?
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Invitation games and the price of stability
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Welfare maximization and the supermodular degree
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Optimization with uniform size queries
Algorithmica | 2017-05-11 | Paper |
Chasing Ghosts: Competing with Stateful Policies
SIAM Journal on Computing | 2017-03-10 | Paper |
Finding hidden cliques in linear time
| 2017-02-10 | Paper |
Nonmonotonic phenomena in packet routing
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Two prover protocols, low error at affordable rates
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
A minimal model for secure computation (extended abstract)
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Finding OR in a noisy broadcast network
Information Processing Letters | 2016-06-16 | Paper |
On giant components and treewidth in the layers model
Random Structures & Algorithms | 2016-06-10 | Paper |
Oblivious algorithms for the maximum directed cut problem
Algorithmica | 2015-05-26 | Paper |
Short random walks on graphs
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
On the integrality ratio of semidefinite relaxations of MAX CUT
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Recoverable values for independent sets
Random Structures & Algorithms | 2015-02-20 | Paper |
On fair division of a homogeneous good
Games and Economic Behavior | 2015-01-14 | Paper |
Musical Chairs
SIAM Journal on Discrete Mathematics | 2014-12-22 | Paper |
On maximizing welfare when utility functions are subadditive
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Finding small balanced separators
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Complete convergence of message passing algorithms for some satisfiability problems
Theory of Computing | 2014-10-06 | Paper |
Approximating the minimum bisection size (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Approximating the domatic number
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Santa claus meets hypergraph matchings
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Min-max Graph Partitioning and Small Set Expansion
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Demand Queries with Preprocessing
Automata, Languages, and Programming | 2014-07-01 | Paper |
Mechanism design with uncertain inputs
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Short Tours through Large Linear Forests
Integer Programming and Combinatorial Optimization | 2014-06-02 | Paper |
On robustly asymmetric graphs
| 2014-02-05 | Paper |
Connectivity of random high dimensional geometric graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Universal factor graphs
Automata, Languages, and Programming | 2013-08-12 | Paper |
A greedy approximation algorithm for minimum-gap scheduling
Lecture Notes in Computer Science | 2013-06-07 | Paper |
PASS approximation: a framework for analyzing and designing heuristics
Algorithmica | 2013-05-13 | Paper |
Buffer management for colored packets with deadlines
Theory of Computing Systems | 2012-12-10 | Paper |
On estimation algorithms vs approximation algorithms
| 2012-10-19 | Paper |
Maximizing Non-monotone Submodular Functions
SIAM Journal on Computing | 2011-11-07 | Paper |
Oblivious Collaboration
Lecture Notes in Computer Science | 2011-10-28 | Paper |
On the diameter of the set of satisfying assignments in random satisfiable \(k\)-CNF formulas
SIAM Journal on Discrete Mathematics | 2011-10-27 | Paper |
An \(O(n \log n)\) algorithm for a load balancing problem on paths
Lecture Notes in Computer Science | 2011-08-12 | Paper |
Recoverable values for independent sets
Lecture Notes in Computer Science | 2011-07-06 | Paper |
On optimal strategies for a hat game on graphs
SIAM Journal on Discrete Mathematics | 2011-06-17 | Paper |
scientific article; zbMATH DE number 5899254 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
The submodular welfare problem with demand queries
Theory of Computing | 2011-05-24 | Paper |
Hardness results for approximating the bandwidth
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Balanced coloring of bipartite graphs
Journal of Graph Theory | 2010-11-24 | Paper |
Responsive lotteries
Algorithmic Game Theory | 2010-10-19 | Paper |
A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
Algorithmic Game Theory | 2010-10-19 | Paper |
Improved approximation algorithms for minimum-weight vertex separators
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Combination can be hard
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
scientific article; zbMATH DE number 5764883 (Why is no real title available?)
| 2010-08-06 | Paper |
Relations between average case complexity and approximation complexity
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
A preemptive algorithm for maximizing disjoint paths on trees
Algorithmica | 2010-05-19 | Paper |
On maximizing welfare when utility functions are subadditive
SIAM Journal on Computing | 2010-03-17 | Paper |
An improved approximation ratio for the minimum linear arrangement problem
Information Processing Letters | 2010-01-29 | Paper |
On the hardness of approximating max-satisfy
Information Processing Letters | 2009-12-18 | Paper |
PASS Approximation
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Combination Can Be Hard: Approximability of the Unique Coverage Problem
SIAM Journal on Computing | 2009-08-20 | Paper |
Approximating the bandwidth of caterpillars
Algorithmica | 2009-07-24 | Paper |
Finding a Maximum Independent Set in a Sparse Random Graph
SIAM Journal on Discrete Mathematics | 2009-05-27 | Paper |
Improved Approximation Algorithms for Minimum Weight Vertex Separators
SIAM Journal on Computing | 2009-04-30 | Paper |
On the complexity of finding balanced oneway cuts
Information Processing Letters | 2009-04-28 | Paper |
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Small Linear Dependencies for Binary Vectors of Low Weight
Bolyai Society Mathematical Studies | 2009-02-12 | Paper |
Santa Claus Meets Hypergraph Matchings
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Edge Coloring and Decompositions of Weighted Graphs
Algorithms - ESA 2008 | 2008-11-25 | Paper |
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees
Algorithm Theory – SWAT 2008 | 2008-07-15 | Paper |
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
The RPR2 rounding technique for semidefinite programs
Journal of Algorithms | 2006-08-14 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
| 2006-07-07 | Paper |
A Polylogarithmic Approximation of the Minimum Bisection
SIAM Review | 2006-06-01 | Paper |
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
SIAM Journal on Computing | 2006-06-01 | Paper |
Improved approximation of the minimum cover time
Theoretical Computer Science | 2005-09-22 | Paper |
Spectral techniques applied to sparse random graphs
Random Structures & Algorithms | 2005-09-22 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Approximating Maximum Clique by Removing Subgraphs
SIAM Journal on Discrete Mathematics | 2005-02-28 | Paper |
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
SIAM Journal on Computing | 2005-02-21 | Paper |
A threshold of ln n for approximating set cover
Journal of the ACM | 2005-01-25 | Paper |
Approximating min sum set cover
Algorithmica | 2004-11-05 | Paper |
The inapproximability of lattice and coding problems with preprocessing
Journal of Computer and System Sciences | 2004-10-04 | Paper |
Error reduction by parallel repetition - a negative result
Combinatorica | 2003-08-06 | Paper |
Deterministic approximation of the cover time
Random Structures & Algorithms | 2003-08-06 | Paper |
scientific article; zbMATH DE number 1947050 (Why is no real title available?)
| 2003-07-07 | Paper |
scientific article; zbMATH DE number 1947051 (Why is no real title available?)
| 2003-07-07 | Paper |
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
SIAM Journal on Computing | 2003-06-19 | Paper |
On cutting a few vertices from a graph
Discrete Applied Mathematics | 2003-06-10 | Paper |
On the drift of short schedules.
Theoretical Computer Science | 2003-01-21 | Paper |
Approximating theDomatic Number
SIAM Journal on Computing | 2003-01-05 | Paper |
Improved approximation of Max-Cut on graphs of bounded degree
Journal of Algorithms | 2002-09-30 | Paper |
scientific article; zbMATH DE number 1775452 (Why is no real title available?)
| 2002-09-17 | Paper |
scientific article; zbMATH DE number 1775392 (Why is no real title available?)
| 2002-09-17 | Paper |
scientific article; zbMATH DE number 1789921 (Why is no real title available?)
| 2002-08-27 | Paper |
A note on approximating Max-Bisection on regular graphs
Information Processing Letters | 2002-07-14 | Paper |
Approximation algorithms for maximization problems arising in graph partitioning
Journal of Algorithms | 2002-07-08 | Paper |
Heuristics for semirandom graph problems
Journal of Computer and System Sciences | 2002-07-04 | Paper |
On the optimality of the random hyperplane rounding technique for MAX CUT
Random Structures & Algorithms | 2002-07-01 | Paper |
scientific article; zbMATH DE number 1754595 (Why is no real title available?)
| 2002-06-12 | Paper |
A polylogarithmic approximation of the minimum bisection
SIAM Journal on Computing | 2002-04-23 | Paper |
scientific article; zbMATH DE number 1256693 (Why is no real title available?)
| 2002-01-16 | Paper |
scientific article; zbMATH DE number 1670535 (Why is no real title available?)
| 2001-11-11 | Paper |
scientific article; zbMATH DE number 1617243 (Why is no real title available?)
| 2001-07-11 | Paper |
The dense \(k\)-subgraph problem
Algorithmica | 2001-04-17 | Paper |
On the hardness of computing the permanent of random matrices
Computational Complexity | 2001-03-15 | Paper |
scientific article; zbMATH DE number 1559566 (Why is no real title available?)
| 2001-02-28 | Paper |
Two-Prover Protocols---Low Error at Affordable Rates
SIAM Journal on Computing | 2000-10-18 | Paper |
Approximating the bandwidth via volume respecting embeddings
Journal of Computer and System Sciences | 2000-08-27 | Paper |
On the cost of recomputing: Tight bounds on pebbling with faults
Theoretical Computer Science | 2000-08-23 | Paper |
scientific article; zbMATH DE number 1445298 (Why is no real title available?)
| 2000-05-10 | Paper |
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
SIAM Journal on Computing | 1999-10-28 | Paper |
scientific article; zbMATH DE number 1256748 (Why is no real title available?)
| 1999-10-18 | Paper |
Zero knowledge and the chromatic number
Journal of Computer and System Sciences | 1999-10-06 | Paper |
scientific article; zbMATH DE number 1332665 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 1999-09-08 | Paper |
scientific article; zbMATH DE number 708807 (Why is no real title available?)
| 1999-08-30 | Paper |
scientific article; zbMATH DE number 1263222 (Why is no real title available?)
| 1999-06-29 | Paper |
scientific article; zbMATH DE number 1256784 (Why is no real title available?)
| 1999-03-01 | Paper |
Collecting coupons on trees, and the cover time of random walks
Computational Complexity | 1998-10-19 | Paper |
Interactive proofs and the hardness of approximating cliques
Journal of the ACM | 1998-01-21 | Paper |
Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
Combinatorica | 1998-01-05 | Paper |
A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
Journal of Computer and System Sciences | 1998-01-04 | Paper |
scientific article; zbMATH DE number 1024047 (Why is no real title available?)
| 1997-12-15 | Paper |
A fast randomized LOGSPACE algorithm for graph connectivity
Theoretical Computer Science | 1997-02-27 | Paper |
Random Walks on Regular and Irregular Graphs
SIAM Journal on Discrete Mathematics | 1996-12-09 | Paper |
Short Random Walks on Graphs
SIAM Journal on Discrete Mathematics | 1996-04-24 | Paper |
A tight lower bound on the cover time for random walks on graphs
Random Structures & Algorithms | 1996-02-20 | Paper |
Derandomized graph products
Computational Complexity | 1995-07-16 | Paper |
A tight upper bound on the cover time for random walks on graphs
Random Structures & Algorithms | 1995-04-19 | Paper |
Randomized graph products, chromatic numbers, and Lovasz j-function
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 | 1995-01-01 | Paper |
Computing with Noisy Information
SIAM Journal on Computing | 1994-11-29 | Paper |
On the complexity of finite random functions
Information Processing Letters | 1993-05-16 | Paper |
Multi-oracle interactive protocols with constant space verifiers
Journal of Computer and System Sciences | 1992-09-27 | Paper |
scientific article; zbMATH DE number 4191107 (Why is no real title available?)
| 1991-01-01 | Paper |
scientific article; zbMATH DE number 4191106 (Why is no real title available?)
| 1990-01-01 | Paper |
Randomized broadcast in networks
Random Structures & Algorithms | 1990-01-01 | Paper |
Zero-knowledge proofs of identity
Journal of Cryptology | 1988-01-01 | Paper |
