Uriel Feige

Vadim Grinberg

Theory Comput. Syst., August, 2024

Low communication protocols for fair allocation of indivisible goods.

[BibT_eX]

[DOI]

CoRR, 2024

Share-Based Fairness for Arbitrary Entitlements.

[BibT_eX]

[DOI]

CoRR, 2024

2023

The inversion paradox, and classification of fairness notions.

[BibT_eX]

[DOI]

CoRR, 2023

On Fair Allocation of Indivisible Goods to Submodular Agents.

[BibT_eX]

[DOI]

Gilad Ben Uziahu

CoRR, 2023

On picking sequences for chores.

[BibT_eX]

[DOI]

Xin Huang

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

2022

Max-Min Greedy Matching.

[BibT_eX]

[DOI]

Alon Eden

Theory Comput., 2022

On the path partition number of 6-regular graphs.

[BibT_eX]

[DOI]

Ella Fuchs

J. Graph Theory, 2022

Improved maximin fair allocation of indivisible items to three agents.

[BibT_eX]

[DOI]

Alexey Norkin

CoRR, 2022

On allocations that give intersecting groups their fair share.

[BibT_eX]

[DOI]

Yehonatan Tahan

CoRR, 2022

On Best-of-Both-Worlds Fair-Share Allocations.

[BibT_eX]

[DOI]

Tomer Ezra

Proceedings of the Web and Internet Economics - 18th International Conference, 2022

Fair Allocations for Smoothed Utilities.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Target set selection for conservative populations.

[BibT_eX]

[DOI]

Shimon Kogan

Discret. Appl. Math., 2021

A tight bound for the clique query problem in two rounds.

[BibT_eX]

[DOI]

Tom Ferster

CoRR, 2021

A Tight Negative Example for MMS Fair Allocations.

[BibT_eX]

[DOI]

Ariel Sapir

Laliv Tauber

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Are Gross Substitutes a Substitute for Submodular Valuations?

[BibT_eX]

[DOI]

Shahar Dobzinski

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Fair-Share Allocations for Agents with Arbitrary Entitlements.

[BibT_eX]

[DOI]

Tomer Ezra

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Fair and Truthful Mechanisms for Dichotomous Valuations.

[BibT_eX]

[DOI]

Tomer Ezra

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Shotgun assembly of random jigsaw puzzles.

[BibT_eX]

[DOI]

Charles Bordenave

Elchanan Mossel

Random Struct. Algorithms, July, 2020

On the Profile of Multiplicities of Complete Subgraphs.

[BibT_eX]

[DOI]

Anne Kenyon

Shimon Kogan

SIAM J. Discret. Math., 2020

Approximate Modularity Revisited.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Finding cliques using few probes.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2020

Quantitative Group Testing and the rank of random matrices.

[BibT_eX]

[DOI]

Amir Lellouche

CoRR, 2020

Introduction to Semirandom Models.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

A randomized strategy in the mirror game.

[BibT_eX]

[DOI]

CoRR, 2019

A New Approach to Fair Distribution of Welfare.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 15th International Conference, 2019

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.

[BibT_eX]

[DOI]

Janardhan Kulkarni

Shi Li

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Random Walks with the Minimum Degree Local Rule Have O(n2) Cover Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Tighter bounds for online bipartite matching.

[BibT_eX]

[DOI]

CoRR, 2018

The Ordered Covering Problem.

[BibT_eX]

[DOI]

Yael Hitron

Algorithmica, 2018

On the Probe Complexity of Local Computation Algorithms.

[BibT_eX]

[DOI]

Boaz Patt-Shamir

Shai Vardi

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Robust Inference for Multiclass Classification.

[BibT_eX]

[DOI]

Yishay Mansour

Robert E. Schapire

Proceedings of the Algorithmic Learning Theory, 2018

2017

Chasing Ghosts: Competing with Stateful Policies.

[BibT_eX]

[DOI]

Tomer Koren

SIAM J. Comput., 2017

A greedy approximation algorithm for minimum-gap scheduling.

[BibT_eX]

[DOI]

Marek Chrobak

Mohammad Taghi Hajiaghayi

Sanjeev Khanna

Fei Li

Seffi Naor

J. Sched., 2017

Optimization with Uniform Size Queries.

[BibT_eX]

[DOI]

Algorithmica, 2017

Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

On giant components and treewidth in the layers model.

[BibT_eX]

[DOI]

Jonathan Hermon

Random Struct. Algorithms, 2016

Random walks with the minimum degree local rule have $O(n^2)$ cover time.

[BibT_eX]

[DOI]

CoRR, 2016

On the effect of randomness on planted 3-coloring models.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Oblivious Rounding and the Integrality Gap.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Recoverable values for independent sets.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

Oblivious Algorithms for the Maximum Directed Cut Problem.

[BibT_eX]

[DOI]

Algorithmica, 2015

Contagious Sets in Expanders.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Why are Images Smooth?

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Learning and inference in the presence of corrupted inputs.

[BibT_eX]

[DOI]

Yishay Mansour

Robert E. Schapire

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Musical Chairs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Min-Max Graph Partitioning and Small Set Expansion.

[BibT_eX]

[DOI]

Nikhil Bansal

Konstantin Makarychev

Viswanath Nagarajan

Joseph Naor

Roy Schwartz

SIAM J. Comput., 2014

On fair division of a homogeneous good.

[BibT_eX]

[DOI]

Games Econ. Behav., 2014

Separation between Estimation and Approximation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

A Unifying Hierarchy of Valuations with Complements and Substitutes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

NP-hardness of hypercube 2-segmentation.

[BibT_eX]

[DOI]

CoRR, 2014

On robustly asymmetric graphs.

[BibT_eX]

[DOI]

CoRR, 2014

Short Tours through Large Linear Forests.

[BibT_eX]

[DOI]

R. Ravi

Mohit Singh

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Invitation games and the price of stability.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Sequential decision making with vector outcomes.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Demand Queries with Preprocessing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.

[BibT_eX]

[DOI]

Elchanan Mossel

Dan Vilenchik

Theory Comput., 2013

Welfare Maximization and the Supermodular Degree.

[BibT_eX]

[DOI]

Rani Izsak

Electron. Colloquium Comput. Complex., 2013

PASS Approximation: A Framework for Analyzing and Designing Heuristics.

[BibT_eX]

[DOI]

Algorithmica, 2013

Competition among asymmetric sellers with fixed supply.

[BibT_eX]

[DOI]

Ron Lavi

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Connectivity of Random High Dimensional Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

The Cascade Auction - A Mechanism for Deterring Collusion in Auctions.

[BibT_eX]

[DOI]

Gil Kalai

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012

Santa claus meets hypergraph matchings.

[BibT_eX]

[DOI]

Arash Asadpour

Amin Saberi

ACM Trans. Algorithms, 2012

Universal Factor Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Mastering multi-player games.

[BibT_eX]

[DOI]

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 k-CNF Formulas.

[BibT_eX]

[DOI]

Abraham D. Flaxman

Dan Vilenchik

SIAM J. Discret. Math., 2011

Maximizing Non-monotone Submodular Functions.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Jan Vondrák

SIAM J. Comput., 2011

Buffer Management for Colored Packets with Deadlines.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Hardness results for approximating the bandwidth.

[BibT_eX]

[DOI]

Chandan K. Dubey

Walter Unger

J. Comput. Syst. Sci., 2011

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

Oblivious Collaboration.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 25th International Symposium, 2011

An O(n log n) Algorithm for a Load Balancing Problem on Paths.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Mechanism design with uncertain inputs: (to err is human, to forgive divine).

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

The Submodular Welfare Problem with Demand Queries.

[BibT_eX]

[DOI]

Jan Vondrák

Theory Comput., 2010

On Optimal Strategies for a Hat Game on Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Balanced coloring of bipartite graphs.

[BibT_eX]

[DOI]

Shimon Kogan

J. Graph Theory, 2010

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium

[BibT_eX]

[DOI]

CoRR, 2010

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

CoRR, 2010

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.

[BibT_eX]

[DOI]

Yossi Azar

Daniel Glasner

Algorithmica, 2010

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Responsive Lotteries.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

2009

On Maximizing Welfare When Utility Functions Are Subadditive.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Faster FAST(Feedback Arc Set in Tournaments)

[BibT_eX]

[DOI]

CoRR, 2009

Deterministic approximation for the cover time of trees

[BibT_eX]

[DOI]

Ofer Zeitouni

CoRR, 2009

Interchanging distance and capacity in probabilistic mappings

[BibT_eX]

[DOI]

Reid Andersen

CoRR, 2009

Approximating the Bandwidth of Caterpillars.

[BibT_eX]

[DOI]

Kunal Talwar

Algorithmica, 2009

On smoothed k-CNF formulas and the Walksat algorithm.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On the power of two, three and four probes.

[BibT_eX]

[DOI]

Noga Alon

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

PASS Approximation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Improved Approximation Algorithms for Minimum Weight Vertex Separators.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

James R. Lee

SIAM J. Comput., 2008

Combination Can Be Hard: Approximability of the Unique Coverage Problem.

[BibT_eX]

[DOI]

Erik D. Demaine

MohammadTaghi Hajiaghayi

Mohammad R. Salavatipour

SIAM J. Comput., 2008

A combinatorial allocation mechanism with penalties for banner advertising.

[BibT_eX]

[DOI]

Proceedings of the 17th International Conference on World Wide Web, 2008

Trust-based recommendation systems: an axiomatic approach.

[BibT_eX]

[DOI]

Proceedings of the 17th International Conference on World Wide Web, 2008

On allocations that maximize fairness.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On Estimation Algorithms vs Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Edge Coloring and Decompositions of Weighted Graphs.

[BibT_eX]

[DOI]

Mohit Singh

Proceedings of the Algorithms, 2008

2007

Easily refutable subformulas of large random 3CNF formulas.

[BibT_eX]

[DOI]

Theory Comput., 2007

An improved approximation ratio for the minimum linear arrangement problem.

[BibT_eX]

[DOI]

James R. Lee

Inf. Process. Lett., 2007

Understanding Parallel Repetition Requires Understanding Foams.

[BibT_eX]

[DOI]

Guy Kindler

Ryan O'Donnell

Electron. Colloquium Comput. Complex., 2007

Robust Combinatorial Optimization with Exponential Scenarios.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Refuting Smoothed 3CNF Formulas.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Mohit Singh

Proceedings of the Approximation, 2007

2006

On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

The RPR2 rounding technique for semidefinite programs.

[BibT_eX]

[DOI]

J. Algorithms, 2006

On the hardness of approximating Max-Satisfy.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Random 3CNF formulas elude the Lovasz theta function.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Finding small balanced separators.

[BibT_eX]

[DOI]

Mohammad Mahdian

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.

[BibT_eX]

[DOI]

Jan Vondrák

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Witnesses for non-satisfiability of dense random 3CNF formulas.

[BibT_eX]

[DOI]

Jeong Han Kim

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Improved approximation of the minimum cover time.

[BibT_eX]

[DOI]

Eden Chlamtac

Theor. Comput. Sci., 2005

Spectral techniques applied to sparse random graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2005

Genomic Variability within an Organism Exposes Its Cell Lineage Tree.

[BibT_eX]

[DOI]

PLoS Comput. Biol., 2005

Finding a Maximum Independent Set in a Sparse Random Graph

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

On the Competitive Ratio of the Random Sampling Auction.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Rigorous analysis of heuristics for NP-hard problems.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Approximating Maximum Clique by Removing Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.

[BibT_eX]

[DOI]

Gideon Schechtman

SIAM J. Comput., 2004

The inapproximability of lattice and coding problems with preprocessing.

[BibT_eX]

[DOI]

Daniele Micciancio

J. Comput. Syst. Sci., 2004

Approximating Min Sum Set Cover.

[BibT_eX]

[DOI]

László Lovász

Prasad Tetali

Algorithmica, 2004

On Systems of Linear Equations with Two Variables per Equation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Deterministic approximation of the cover time.

[BibT_eX]

[DOI]

Yuri Rabinovich

Random Struct. Algorithms, 2003

On the complexity of finding balanced oneway cuts.

[BibT_eX]

[DOI]

Orly Yahalom

Inf. Process. Lett., 2003

On Cutting a Few Vertices from a Graph.

[BibT_eX]

[DOI]

Kobbi Nissim

Discret. Appl. Math., 2003

Approximation thresholds for combinatorial optimization problems

[BibT_eX]

[DOI]

CoRR, 2003

2002

On the drift of short schedules.

[BibT_eX]

[DOI]

Giora Rayzman

Theor. Comput. Sci., 2002

A Polylogarithmic Approximation of the Minimum Bisection.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Approximating the Domatic Number.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Guy Kortsarz

Aravind Srinivasan

SIAM J. Comput., 2002

On the optimality of the random hyperplane rounding technique for MAX CUT.

[BibT_eX]

[DOI]

Gideon Schechtman

Random Struct. Algorithms, 2002

Error Reduction by Parallel Repetition - A Negative Result.

[BibT_eX]

[DOI]

Oleg Verbitsky

Comb., 2002

Improved Bounds for Acyclic Job Shop Scheduling.

[BibT_eX]

[DOI]

Christian Scheideler

Comb., 2002

Relations between average case complexity and approximation complexity.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Approximating Maximum Edge Coloring in Multigraphs.

[BibT_eX]

[DOI]

Udi Wieder

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

Heuristics for Semirandom Graph Problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning.

[BibT_eX]

[DOI]

J. Algorithms, 2001

A note on approximating Max-Bisection on regular graphs.

[BibT_eX]

[DOI]

Marek Karpinski

Inf. Process. Lett., 2001

The Dense k-Subgraph Problem.

[BibT_eX]

[DOI]

Guy Kortsarz

David Peleg

Algorithmica, 2001

On the integrality ratio of semidefinite relaxations of MAX CUT.

[BibT_eX]

[DOI]

Gideon Schechtman

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.

[BibT_eX]

[DOI]

Yonatan Aumann

Judit Bar-Ilan

Theor. Comput. Sci., 2000

Two-Prover Protocols - Low Error at Affordable Rates.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Finding and certifying a large hidden clique in a semirandom graph.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2000

Approximating the Bandwidth via Volume Respecting Embeddings.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

Finding OR in a noisy broadcast network.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

[BibT_eX]

[DOI]

Marek Karpinski

Electron. Colloquium Comput. Complex., 2000

Networks on Which Hot-Potato Routing Does Not Livelock.

[BibT_eX]

[DOI]

Distributed Comput., 2000

Coping with the NP-Hardness of the Graph Bandwidth Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2000

Approximating the minimum bisection size (extended abstract).

[BibT_eX]

[DOI]

Kobbi Nissim

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Approximating the domatic number.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Guy Kortsarz

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Min-Wise versus linear independence (extended abstract).

[BibT_eX]

[DOI]

Andrei Z. Broder

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

On the hardness of approximating N P witnesses.

[BibT_eX]

[DOI]

Kobbi Nissim

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.

[BibT_eX]

[DOI]

Dror Lapidot

SIAM J. Comput., 1999

Nonmonotonic Phenomena in Packet Routing.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Noncryptographic Selection Protocols.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Zero Knowledge and the Chromatic Number.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

A Threshold of ln n for Approximating Set Cover.

[BibT_eX]

[DOI]

J. ACM, 1998

Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).

[BibT_eX]

[DOI]

Christian Scheideler

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion.

[BibT_eX]

[DOI]

Comb., 1997

On Limited versus Polynomial Nondeterminism.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1997

On the Hardness of Computing the Permanent of Random Matrices.

[BibT_eX]

[DOI]

Carsten Lund

Comput. Complex., 1997

Collecting Coupons on Trees, and the Cover Time of Random Walks.

[BibT_eX]

[DOI]

Comput. Complex., 1997

Making Games Short (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Stereoscopic families of permutations, and their applications.

[BibT_eX]

[DOI]

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996

A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Random Walks on Regular and Irregular Graphs.

[BibT_eX]

[DOI]

Don Coppersmith

James B. Shearer

SIAM J. Discret. Math., 1996

Short Random Walks on Graphs.

[BibT_eX]

[DOI]

Greg Barnes

SIAM J. Discret. Math., 1996

Interactive Proofs and the Hardness of Approximating Cliques.

[BibT_eX]

[DOI]

J. ACM, 1996

A Threshold of ln n for Approximating Set Cover (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Adaptively Secure Multi-Party Computation.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1995

A Tight Upper Bound on the Cover Time for Random Walks on Graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1995

Derandomized Graph Products.

[BibT_eX]

[DOI]

Comput. Complex., 1995

Impossibility results for recycling random bits in two-prover proof systems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Randomized graph products, chromatic numbers, and Lovasz theta-function.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Michel X. Goemans

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Observations on Hot Potato Routing.

[BibT_eX]

[DOI]

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

On the Role of Shared Randomness in Two Prover Proof Systems.

[BibT_eX]

[DOI]

Mihir Bellare

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994

Computing with Noisy Information.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

A minimal model for secure computation (extended abstract).

[BibT_eX]

[DOI]

Moni Naor

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

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

On Message Proof Systems with Known Space Verifiers.

[BibT_eX]

[DOI]

Yonatan Aumann

Proceedings of the Advances in Cryptology, 1993

1992

Multi-Oracle Interactive Protocols with Constant Space Verifiers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

On the Complexity of Finite Random Functions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)

[BibT_eX]

[DOI]

László Lovász

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)

[BibT_eX]

[DOI]

Carsten Lund

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Exact Analysis of Hot-Potato Routing (Extended Abstract)

[BibT_eX]

[DOI]

Prabhakar Raghavan

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Low Communication 2-Prover Zero-Knowledge Proofs for NP.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1992

1991

Approximating Clique is Almost NP-Complete (Preliminary Version)

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Randomized Broadcast in Networks.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1990

Witness Indistinguishable and Witness Hiding Protocols

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Computing with Unreliable Information (Preliminary Version)

[BibT_eX]

[DOI]

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)

[BibT_eX]

[DOI]

Dror Lapidot

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

On Expected Polynomial Time Simulation of Zero Knowledge Protocols.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing And Cryptography, 1989

Zero Knowledge Proofs of Knowledge in Two Rounds.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1989

Multi-Oracle Interactive Protocols with Space Bounded Verifiers.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Zero-Knowledge Proofs of Identity.

[BibT_eX]

[DOI]

Amos Fiat

J. Cryptol., 1988

The Noisy Oracle Problem.

[BibT_eX]

[DOI]