2025
Fair allocations with subadditive and XOS valuations.
CoRR, March, 2025
The Surprising Power of Spectral Refutation.
Commun. ACM, March, 2025
Concentration and maximin fair allocations for subadditive valuations.
CoRR, February, 2025
Share-Based Fairness for Arbitrary Entitlements.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025
2024
Theory Comput. Syst., August, 2024
Fair-Share Allocations for Agents with Arbitrary Entitlements.
Math. Oper. Res., 2024
Low communication protocols for fair allocation of indivisible goods.
CoRR, 2024
2023
The inversion paradox, and classification of fairness notions.
CoRR, 2023
On Fair Allocation of Indivisible Goods to Submodular Agents.
CoRR, 2023
On picking sequences for chores.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023
2022
On the path partition number of 6-regular graphs.
J. Graph Theory, 2022
Improved maximin fair allocation of indivisible items to three agents.
CoRR, 2022
On allocations that give intersecting groups their fair share.
CoRR, 2022
On Best-of-Both-Worlds Fair-Share Allocations.
Proceedings of the Web and Internet Economics - 18th International Conference, 2022
Fair Allocations for Smoothed Utilities.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022
Fair Shares: Feasibility, Domination and Incentives.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022
2021
Navigating in Trees with Permanently Noisy Advice.
ACM Trans. Algorithms, 2021
Target set selection for conservative populations.
Discret. Appl. Math., 2021
A tight bound for the clique query problem in two rounds.
CoRR, 2021
A Tight Negative Example for MMS Fair Allocations.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021
Are Gross Substitutes a Substitute for Submodular Valuations?
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021
Fair and Truthful Mechanisms for Dichotomous Valuations.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021
2020
Shotgun assembly of random jigsaw puzzles.
Random Struct. Algorithms, July, 2020
On the Profile of Multiplicities of Complete Subgraphs.
SIAM J. Discret. Math., 2020
Approximate Modularity Revisited.
SIAM J. Comput., 2020
Finding cliques using few probes.
Random Struct. Algorithms, 2020
Quantitative Group Testing and the rank of random matrices.
CoRR, 2020
Introduction to Semirandom Models.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020
2019
A randomized strategy in the mirror game.
CoRR, 2019
A New Approach to Fair Distribution of Welfare.
Proceedings of the Web and Internet Economics - 15th International Conference, 2019
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
2018
Random Walks with the Minimum Degree Local Rule Have O(n<sup>2)</sup> Cover Time.
SIAM J. Comput., 2018
Tighter bounds for online bipartite matching.
CoRR, 2018
The Ordered Covering Problem.
Algorithmica, 2018
On the Probe Complexity of Local Computation Algorithms.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
Robust Inference for Multiclass Classification.
Proceedings of the Algorithmic Learning Theory, 2018
2017
Chasing Ghosts: Competing with Stateful Policies.
SIAM J. Comput., 2017
A greedy approximation algorithm for minimum-gap scheduling.
J. Sched., 2017
Optimization with Uniform Size Queries.
Algorithmica, 2017
Random Walks with the Minimum Degree Local Rule Have <i>O</i>(<i>N</i><sup>2</sup>) Cover Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
2016
On giant components and treewidth in the layers model.
Random Struct. Algorithms, 2016
Random walks with the minimum degree local rule have $O(n^2)$ cover time.
CoRR, 2016
On the effect of randomness on planted 3-coloring models.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Oblivious Rounding and the Integrality Gap.
Proceedings of the Approximation, 2016
2015
Recoverable values for independent sets.
Random Struct. Algorithms, 2015
Oblivious Algorithms for the Maximum Directed Cut Problem.
Algorithmica, 2015
Contagious Sets in Expanders.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015
Learning and inference in the presence of corrupted inputs.
Proceedings of The 28th Conference on Learning Theory, 2015
2014
SIAM J. Discret. Math., 2014
Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 2014
On fair division of a homogeneous good.
Games Econ. Behav., 2014
Separation between Estimation and Approximation.
Electron. Colloquium Comput. Complex., 2014
A Unifying Hierarchy of Valuations with Complements and Substitutes.
Electron. Colloquium Comput. Complex., 2014
NP-hardness of hypercube 2-segmentation.
CoRR, 2014
On robustly asymmetric graphs.
CoRR, 2014
Short Tours through Large Linear Forests.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014
Invitation games and the price of stability.
Proceedings of the Innovations in Theoretical Computer Science, 2014
Sequential decision making with vector outcomes.
Proceedings of the Innovations in Theoretical Computer Science, 2014
Demand Queries with Preprocessing.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014
2013
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Theory Comput., 2013
Welfare Maximization and the Supermodular Degree.
Electron. Colloquium Comput. Complex., 2013
PASS Approximation: A Framework for Analyzing and Designing Heuristics.
Algorithmica, 2013
Competition among asymmetric sellers with fixed supply.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013
Connectivity of Random High Dimensional Geometric Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013
The Cascade Auction - A Mechanism for Deterring Collusion in Auctions.
Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013
2012
Santa claus meets hypergraph matchings.
ACM Trans. Algorithms, 2012
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Mastering multi-player games.
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012
2011
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable <i>k</i>-CNF Formulas.
SIAM J. Discret. Math., 2011
Maximizing Non-monotone Submodular Functions.
SIAM J. Comput., 2011
Buffer Management for Colored Packets with Deadlines.
Theory Comput. Syst., 2011
Hardness results for approximating the bandwidth.
J. Comput. Syst. Sci., 2011
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011
Proceedings of the Distributed Computing - 25th International Symposium, 2011
An O(n log n) Algorithm for a Load Balancing Problem on Paths.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011
Mechanism design with uncertain inputs: (to err is human, to forgive divine).
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
2010
The Submodular Welfare Problem with Demand Queries.
Theory Comput., 2010
On Optimal Strategies for a Hat Game on Graphs.
SIAM J. Discret. Math., 2010
Balanced coloring of bipartite graphs.
J. Graph Theory, 2010
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
CoRR, 2010
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
CoRR, 2010
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.
Algorithmica, 2010
Detecting high log-densities: an <i>O</i>(<i>n</i><sup>1/4</sup>) approximation for densest <i>k</i>-subgraph.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010
A Direct Reduction from <i>k</i>-Player to 2-Player Approximate Nash Equilibrium.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010
2009
On Maximizing Welfare When Utility Functions Are Subadditive.
SIAM J. Comput., 2009
Faster FAST(Feedback Arc Set in Tournaments)
CoRR, 2009
Deterministic approximation for the cover time of trees
CoRR, 2009
Interchanging distance and capacity in probabilistic mappings
CoRR, 2009
Approximating the Bandwidth of Caterpillars.
Algorithmica, 2009
On smoothed <i>k</i>-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
On the power of two, three and four probes.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Approximation, 2009
2008
Improved Approximation Algorithms for Minimum Weight Vertex Separators.
SIAM J. Comput., 2008
Combination Can Be Hard: Approximability of the Unique Coverage Problem.
SIAM J. Comput., 2008
A combinatorial allocation mechanism with penalties for banner advertising.
Proceedings of the 17th International Conference on World Wide Web, 2008
Trust-based recommendation systems: an axiomatic approach.
Proceedings of the 17th International Conference on World Wide Web, 2008
On allocations that maximize fairness.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
On Estimation Algorithms vs Approximation Algorithms.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008
Edge Coloring and Decompositions of Weighted Graphs.
Proceedings of the Algorithms, 2008
2007
Easily refutable subformulas of large random 3CNF formulas.
Theory Comput., 2007
An improved approximation ratio for the minimum linear arrangement problem.
Inf. Process. Lett., 2007
Understanding Parallel Repetition Requires Understanding Foams.
Electron. Colloquium Comput. Complex., 2007
Robust Combinatorial Optimization with Exponential Scenarios.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007
Refuting Smoothed 3CNF Formulas.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs.
Proceedings of the Approximation, 2007
2006
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph.
SIAM J. Comput., 2006
The RPR<sup>2</sup> rounding technique for semidefinite programs.
J. Algorithms, 2006
On the hardness of approximating Max-Satisfy.
Inf. Process. Lett., 2006
Random 3CNF formulas elude the Lovasz theta function.
Electron. Colloquium Comput. Complex., 2006
Finding small balanced separators.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
Witnesses for non-satisfiability of dense random 3CNF formulas.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
2005
Improved approximation of the minimum cover time.
Theor. Comput. Sci., 2005
Spectral techniques applied to sparse random graphs.
Random Struct. Algorithms, 2005
Genomic Variability within an Organism Exposes Its Cell Lineage Tree.
PLoS Comput. Biol., 2005
Finding a Maximum Independent Set in a Sparse Random Graph
Electron. Colloquium Comput. Complex., 2005
On the Competitive Ratio of the Random Sampling Auction.
Proceedings of the Internet and Network Economics, First International Workshop, 2005
Rigorous analysis of heuristics for NP-hard problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
2004
Approximating Maximum Clique by Removing Subgraphs.
SIAM J. Discret. Math., 2004
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
SIAM J. Comput., 2004
The inapproximability of lattice and coding problems with preprocessing.
J. Comput. Syst. Sci., 2004
Approximating Min Sum Set Cover.
Algorithmica, 2004
On Systems of Linear Equations with Two Variables per Equation.
Proceedings of the Approximation, 2004
2003
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.
SIAM J. Comput., 2003
Deterministic approximation of the cover time.
Random Struct. Algorithms, 2003
On the complexity of finding balanced oneway cuts.
Inf. Process. Lett., 2003
On Cutting a Few Vertices from a Graph.
Discret. Appl. Math., 2003
Approximation thresholds for combinatorial optimization problems
CoRR, 2003
2002
On the drift of short schedules.
Theor. Comput. Sci., 2002
A Polylogarithmic Approximation of the Minimum Bisection.
SIAM J. Comput., 2002
Approximating the Domatic Number.
SIAM J. Comput., 2002
On the optimality of the random hyperplane rounding technique for MAX CUT.
Random Struct. Algorithms, 2002
Error Reduction by Parallel Repetition - A Negative Result.
Comb., 2002
Improved Bounds for Acyclic Job Shop Scheduling.
Comb., 2002
Relations between average case complexity and approximation complexity.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Approximating Maximum Edge Coloring in Multigraphs.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002
2001
Heuristics for Semirandom Graph Problems.
J. Comput. Syst. Sci., 2001
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning.
J. Algorithms, 2001
A note on approximating Max-Bisection on regular graphs.
Inf. Process. Lett., 2001
The Dense <i>k</i>-Subgraph Problem.
Algorithmica, 2001
On the integrality ratio of semidefinite relaxations of MAX CUT.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
2000
On the cost of recomputing: Tight bounds on pebbling with faults.
Theor. Comput. Sci., 2000
Two-Prover Protocols - Low Error at Affordable Rates.
SIAM J. Comput., 2000
Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms, 2000
Approximating the Bandwidth via Volume Respecting Embeddings.
J. Comput. Syst. Sci., 2000
Finding OR in a noisy broadcast network.
Inf. Process. Lett., 2000
Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Electron. Colloquium Comput. Complex., 2000
Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Comput., 2000
Coping with the NP-Hardness of the Graph Bandwidth Problem.
Proceedings of the Algorithm Theory, 2000
Approximating the minimum bisection size (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Approximating the domatic number.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Min-Wise versus linear independence (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
On the hardness of approximating <i>N P</i> witnesses.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000
1999
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.
SIAM J. Comput., 1999
Nonmonotonic Phenomena in Packet Routing.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example.
Proceedings of the Randomization, 1999
Noncryptographic Selection Protocols.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Zero Knowledge and the Chromatic Number.
J. Comput. Syst. Sci., 1998
A Threshold of ln <i>n</i> for Approximating Set Cover.
J. ACM, 1998
Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity.
J. Comput. Syst. Sci., 1997
Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion.
Comb., 1997
On Limited versus Polynomial Nondeterminism.
Chic. J. Theor. Comput. Sci., 1997
On the Hardness of Computing the Permanent of Random Matrices.
Comput. Complex., 1997
Collecting Coupons on Trees, and the Cover Time of Random Walks.
Comput. Complex., 1997
Making Games Short (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Stereoscopic families of permutations, and their applications.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997
1996
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
Theor. Comput. Sci., 1996
Random Walks on Regular and Irregular Graphs.
SIAM J. Discret. Math., 1996
Short Random Walks on Graphs.
SIAM J. Discret. Math., 1996
Interactive Proofs and the Hardness of Approximating Cliques.
J. ACM, 1996
A Threshold of ln <i>n</i> for Approximating Set Cover (Preliminary Version).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
Adaptively Secure Multi-Party Computation.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
1995
A Tight Lower Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms, 1995
A Tight Upper Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms, 1995
Derandomized Graph Products.
Comput. Complex., 1995
Impossibility results for recycling random bits in two-prover proof systems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
Randomized graph products, chromatic numbers, and Lovasz theta-function.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995
Observations on Hot Potato Routing.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995
On the Role of Shared Randomness in Two Prover Proof Systems.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995
1994
Computing with Noisy Information.
SIAM J. Comput., 1994
A minimal model for secure computation (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
1993
A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
On Message Proof Systems with Known Space Verifiers.
Proceedings of the Advances in Cryptology, 1993
1992
Multi-Oracle Interactive Protocols with Constant Space Verifiers.
J. Comput. Syst. Sci., 1992
On the Complexity of Finite Random Functions.
Inf. Process. Lett., 1992
Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
Exact Analysis of Hot-Potato Routing (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Low Communication 2-Prover Zero-Knowledge Proofs for NP.
Proceedings of the Advances in Cryptology, 1992
1991
Approximating Clique is Almost NP-Complete (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
On the Success Probability of the Two Provers in One-Round Proof Systems.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991
1990
Randomized Broadcast in Networks.
Random Struct. Algorithms, 1990
Witness Indistinguishable and Witness Hiding Protocols
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
Computing with Unreliable Information (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
1989
On Expected Polynomial Time Simulation of Zero Knowledge Protocols.
Proceedings of the Distributed Computing And Cryptography, 1989
Zero Knowledge Proofs of Knowledge in Two Rounds.
Proceedings of the Advances in Cryptology, 1989
Multi-Oracle Interactive Protocols with Space Bounded Verifiers.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989
1988
Zero-Knowledge Proofs of Identity.
J. Cryptol., 1988
The Noisy Oracle Problem.
Proceedings of the Advances in Cryptology, 1988