Uriel Feige

Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh: PASS Approximation: A Framework for Analyzing and Designing Heuristics. Algorithmica 66(2): 450-478 (2013)

Uriel Feige, Rani Izsak: Welfare maximization and the supermodular degree. ITCS 2013: 247-256

Arash Asadpour, Uriel Feige, Amin Saberi: Santa claus meets hypergraph matchings. ACM Transactions on Algorithms 8(3): 24 (2012)

Yossi Azar, Uriel Feige, Moshe Tennenholtz, Michal Feldman: Mastering multi-player games. AAMAS 2012: 897-904

Uriel Feige, Shlomo Jozeph: Universal Factor Graphs. ICALP (1) 2012: 339-350

Uriel Feige, Shlomo Jozeph: Universal Factor Graphs. CoRR abs/1204.6484 (2012)

Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov: Musical chairs. CoRR abs/1208.0813 (2012)

Chandan K. Dubey, Uriel Feige, Walter Unger: Hardness results for approximating the bandwidth. J. Comput. Syst. Sci. 77(1): 62-90 (2011)

Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra: Buffer Management for Colored Packets with Deadlines. Theory Comput. Syst. 49(4): 738-756 (2011)

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: Maximizing Non-monotone Submodular Functions. SIAM J. Comput. 40(4): 1133-1153 (2011)

Uriel Feige, Abraham D. Flaxman, Dan Vilenchik: On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas. SIAM J. Discrete Math. 25(2): 736-749 (2011)

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz: Min-max Graph Partitioning and Small Set Expansion. FOCS 2011: 17-26

Uriel Feige, Daniel Reichman: Recoverable Values for Independent Sets. ICALP (1) 2011: 486-497

Uriel Feige, Moshe Tennenholtz: Mechanism design with uncertain inputs: (to err is human, to forgive divine). STOC 2011: 549-558

Nikhil R. Devanur, Uriel Feige: An O(n log n) Algorithm for a Load Balancing Problem on Paths. WADS 2011: 326-337

Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov: Oblivious Collaboration. DISC 2011: 489-504

Uriel Feige, Moshe Tennenholtz: Mechanism design with uncertain inputs (to err is human, to forgive divine). CoRR abs/1103.2520 (2011)

Uriel Feige, Daniel Reichman: Recoverable Values for Independent Sets. CoRR abs/1103.5609 (2011)

Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov: Oblivious Collaboration. CoRR abs/1106.2065 (2011)

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz: Min-Max Graph Partitioning and Small Set Expansion. CoRR abs/1110.4319 (2011)

Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski: Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1(6): 24-53 (2011)

Yossi Azar, Uriel Feige, Daniel Glasner: A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. Algorithmica 57(3): 517-537 (2010)

Uriel Feige, Shimon Kogan: Balanced coloring of bipartite graphs. Journal of Graph Theory 64(4): 277-291 (2010)

Uriel Feige: On Optimal Strategies for a Hat Game on Graphs. SIAM J. Discrete Math. 24(3): 782-791 (2010)

Uriel Feige, Jan Vondrák: The Submodular Welfare Problem with Demand Queries. Theory of Computing 6(1): 247-290 (2010)

Uriel Feige, Inbal Talgam-Cohen: A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium. SAGT 2010: 138-149

Uriel Feige, Moshe Tennenholtz: Responsive Lotteries. SAGT 2010: 150-161

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan: Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph. STOC 2010: 201-210

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan: Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph. CoRR abs/1001.2891 (2010)

Uriel Feige, Inbal Talgam-Cohen: A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium. CoRR abs/1007.3886 (2010)

Uriel Feige, Shlomo Jozeph: Oblivious Algorithms for the Maximum Directed Cut Problem. CoRR abs/1010.0406 (2010)

Uriel Feige, Kunal Talwar: Approximating the Bandwidth of Caterpillars. Algorithmica 55(1): 190-204 (2009)

Uriel Feige: On Maximizing Welfare When Utility Functions Are Subadditive. SIAM J. Comput. 39(1): 122-142 (2009)

Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh: PASS Approximation. APPROX-RANDOM 2009: 111-124

Noga Alon, Uriel Feige: On the power of two, three and four probes. SODA 2009: 346-354

Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. SODA 2009: 451-460

Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra: Buffer management for colored packets with deadlines. SPAA 2009: 319-327

Reid Andersen, Uriel Feige: Interchanging distance and capacity in probabilistic mappings. CoRR abs/0907.3631 (2009)

Uriel Feige, Ofer Zeitouni: Deterministic approximation for the cover time of trees. CoRR abs/0909.2005 (2009)

Uriel Feige: Faster FAST(Feedback Arc Set in Tournaments). CoRR abs/0911.5094 (2009)

Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008)

Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour: Combination Can Be Hard: Approximability of the Unique Coverage Problem. SIAM J. Comput. 38(4): 1464-1483 (2008)

Uriel Feige, Eran Ofek: Finding a Maximum Independent Set in a Sparse Random Graph. SIAM J. Discrete Math. 22(2): 693-718 (2008)

Arash Asadpour, Uriel Feige, Amin Saberi: Santa Claus Meets Hypergraph Matchings. APPROX-RANDOM 2008: 10-20

Uriel Feige, Mohit Singh: Edge Coloring and Decompositions of Weighted Graphs. ESA 2008: 405-416

Uriel Feige: On Estimation Algorithms vs Approximation Algorithms. FSTTCS 2008: 357-363

Uriel Feige: On allocations that maximize fairness. SODA 2008: 287-293

Yossi Azar, Uriel Feige, Daniel Glasner: A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. SWAT 2008: 319-330

Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh: A combinatorial allocation mechanism with penalties for banner advertising. WWW 2008: 169-178

Reid Andersen, Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman, Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz: Trust-based recommendation systems: an axiomatic approach. WWW 2008: 199-208

Uriel Feige, James R. Lee: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1): 26-29 (2007)

Uriel Feige, Eran Ofek: Easily refutable subformulas of large random 3CNF formulas. Theory of Computing 3(1): 25-43 (2007)

Uriel Feige, Mohit Singh: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. APPROX-RANDOM 2007: 104-118

Uriel Feige, Guy Kindler, Ryan O'Donnell: Understanding Parallel Repetition Requires Understanding Foams. IEEE Conference on Computational Complexity 2007: 179-192

Uriel Feige: Refuting Smoothed 3CNF Formulas. FOCS 2007: 407-417

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: Maximizing Non-Monotone Submodular Functions. FOCS 2007: 461-471

Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni: Robust Combinatorial Optimization with Exponential Scenarios. IPCO 2007: 439-453

David S. Johnson, Uriel Feige (Eds.): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM 2007, isbn 978-1-59593-631-8

Uriel Feige, Guy Kindler, Ryan O'Donnell: Understanding Parallel Repetition Requires Understanding Foams. Electronic Colloquium on Computational Complexity (ECCC) 14(043) (2007)

Uriel Feige, Daniel Reichman: On the hardness of approximating Max-Satisfy. Inf. Process. Lett. 97(1): 31-35 (2006)

Uriel Feige, Michael Langberg: The RPR² rounding technique for semidefinite programs. J. Algorithms 60(1): 1-23 (2006)

Uriel Feige: On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM J. Comput. 35(4): 964-984 (2006)

Uriel Feige, Elchanan Mossel, Dan Vilenchik: Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. APPROX-RANDOM 2006: 339-350

Uriel Feige, Jeong Han Kim, Eran Ofek: Witnesses for non-satisfiability of dense random 3CNF formulas. FOCS 2006: 497-508

Uriel Feige, Jan Vondrák: Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. FOCS 2006: 667-676

Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour: Combination can be hard: approximability of the unique coverage problem. SODA 2006: 162-171

Uriel Feige: On maximizing welfare when utility functions are subadditive. STOC 2006: 41-50

Uriel Feige, Mohammad Mahdian: Finding small balanced separators. STOC 2006: 375-384

Uriel Feige, Eran Ofek: Random 3CNF formulas elude the Lovasz theta function. CoRR abs/cs/0603084 (2006)

Eran Ofek, Uriel Feige: Random 3CNF formulas elude the Lovasz theta function. Electronic Colloquium on Computational Complexity (ECCC) 13(043) (2006)

Dan Frumkin, Adam Wasserstrom, Shai Kaplan, Uriel Feige, Ehud Y. Shapiro: Genomic Variability within an Organism Exposes Its Cell Lineage Tree. PLoS Computational Biology 1(6) (2005)

Uriel Feige, Eran Ofek: Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2): 251-275 (2005)

Eden Chlamtac, Uriel Feige: Improved approximation of the minimum cover time. Theor. Comput. Sci. 341(1-3): 22-38 (2005)

Uriel Feige, Kunal Talwar: Approximating the Bandwidth of Caterpillars. APPROX-RANDOM 2005: 62-73

Uriel Feige, Eran Ofek: Finding a Maximum Independent Set in a Sparse Random Graph. APPROX-RANDOM 2005: 282-293

Uriel Feige: Rigorous analysis of heuristics for NP-hard problems. SODA 2005: 927

Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee: Improved approximation algorithms for minimum-weight vertex separators. STOC 2005: 563-572

Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert D. Kleinberg: On the Competitive Ratio of the Random Sampling Auction. WINE 2005: 878-886

Uriel Feige, Eran Ofek: Finding a Maximum Independent Set in a Sparse Random Graph. Electronic Colloquium on Computational Complexity (ECCC)(050) (2005)

Uriel Feige, László Lovász, Prasad Tetali: Approximating Min Sum Set Cover. Algorithmica 40(4): 219-234 (2004)

Uriel Feige, Daniele Micciancio: The inapproximability of lattice and coding problems with preprocessing. J. Comput. Syst. Sci. 69(1): 45-67 (2004)

Uriel Feige, Michael Langberg, Gideon Schechtman: Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. SIAM J. Comput. 33(6): 1338-1368 (2004)

Uriel Feige: Approximating Maximum Clique by Removing Subgraphs. SIAM J. Discrete Math. 18(2): 219-225 (2004)

Uriel Feige, Daniel Reichman: On Systems of Linear Equations with Two Variables per Equation. APPROX-RANDOM 2004: 117-127

Uriel Feige, Eran Ofek: Easily Refutable Subformulas of Large Random 3CNF Formulas. ICALP 2004: 519-530

Uriel Feige: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. STOC 2004: 594-603

Uriel Feige, Daniel Reichman: On The Hardness of Approximating Max-Satisfy. Electronic Colloquium on Computational Complexity (ECCC)(119) (2004)

Uriel Feige, Robert Krauthgamer, Kobbi Nissim: On Cutting a Few Vertices from a Graph. Discrete Applied Mathematics 127(3): 643-649 (2003)

Uriel Feige, Orly Yahalom: On the complexity of finding balanced oneway cuts. Inf. Process. Lett. 87(1): 1-5 (2003)

Uriel Feige, Yuri Rabinovich: Deterministic approximation of the cover time. Random Struct. Algorithms 23(1): 1-22 (2003)

Uriel Feige, Robert Krauthgamer: The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput. 32(2): 345-370 (2003)

Uriel Feige: Approximation thresholds for combinatorial optimization problems. CoRR cs.CC/0304039 (2003)

Uriel Feige, Christian Scheideler: Improved Bounds for Acyclic Job Shop Scheduling. Combinatorica 22(3): 361-399 (2002)

Uriel Feige, Oleg Verbitsky: Error Reduction by Parallel Repetition - A Negative Result. Combinatorica 22(4): 461-478 (2002)

Uriel Feige, Marek Karpinski, Michael Langberg: Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms 43(2): 201-219 (2002)

Uriel Feige, Gideon Schechtman: On the optimality of the random hyperplane rounding technique for MAX CUT. Random Struct. Algorithms 20(3): 403-440 (2002)

Uriel Feige, Robert Krauthgamer: A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. 31(4): 1090-1118 (2002)

Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan: Approximating the Domatic Number. SIAM J. Comput. 32(1): 172-195 (2002)

Uriel Feige, Giora Rayzman: On the drift of short schedules. Theor. Comput. Sci. 289(1): 473-484 (2002)

Uriel Feige, László Lovász, Prasad Tetali: Approximating Min-sum Set Cover. APPROX 2002: 94-107

Uriel Feige, Eran Ofek, Udi Wieder: Approximating Maximum Edge Coloring in Multigraphs. APPROX 2002: 108-121

Uriel Feige: Relations between Average Case Complexity and Approximation Complexity. IEEE Conference on Computational Complexity 2002: 5

Uriel Feige, Daniele Micciancio: The Inapproximability of Lattice and Coding Problems with Preprocessing. IEEE Conference on Computational Complexity 2002: 44-52

Uriel Feige, Michael Langberg, Gideon Schechtman: Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. FOCS 2002: 283-292

Uriel Feige: Relations between average case complexity and approximation complexity. STOC 2002: 534-543

Uriel Feige, Guy Kortsarz, David Peleg: The Dense k-Subgraph Problem. Algorithmica 29(3): 410-421 (2001)

Uriel Feige, Marek Karpinski, Michael Langberg: A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. 79(4): 181-188 (2001)

Uriel Feige, Michael Langberg: Approximation Algorithms for Maximization Problems Arising in Graph Partitioning. J. Algorithms 41(2): 174-211 (2001)

Uriel Feige, Joe Kilian: Heuristics for Semirandom Graph Problems. J. Comput. Syst. Sci. 63(4): 639-671 (2001)

Uriel Feige, Michael Langberg: The RPR² Rounding Technique for Semidefinite Programs. ICALP 2001: 213-224

Uriel Feige, Gideon Schechtman: On the integrality ratio of semidefinite relaxations of MAX CUT. STOC 2001: 433-442

Uriel Feige, Robert Krauthgamer: Networks on Which Hot-Potato Routing Does Not Livelock. Distributed Computing 13(1): 53-58 (2000)

Uriel Feige, Joe Kilian: Finding OR in a noisy broadcast network. Inf. Process. Lett. 73(1-2): 69-75 (2000)

Uriel Feige: Approximating the Bandwidth via Volume Respecting Embeddings. J. Comput. Syst. Sci. 60(3): 510-539 (2000)

Uriel Feige, Robert Krauthgamer: Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16(2): 195-208 (2000)

Uriel Feige, Joe Kilian: Two-Prover Protocols - Low Error at Affordable Rates. SIAM J. Comput. 30(1): 324-346 (2000)

Yonatan Aumann, Judit Bar-Ilan, Uriel Feige: On the cost of recomputing: Tight bounds on pebbling with faults. Theor. Comput. Sci. 233(1-2): 247-261 (2000)

Uriel Feige, Michael Langberg, Kobbi Nissim: On the hardness of approximating N P witnesses. APPROX 2000: 120-131

Uriel Feige, Robert Krauthgamer: A polylogarithmic approximation of the minimum bisection. FOCS 2000: 105-115

Andrei Z. Broder, Uriel Feige: Min-Wise versus linear independence (extended abstract). SODA 2000: 147-154

Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz: Approximating the domatic number. STOC 2000: 134-143

Uriel Feige, Robert Krauthgamer, Kobbi Nissim: Approximating the minimum bisection size (extended abstract). STOC 2000: 530-536

Uriel Feige: Coping with the NP-Hardness of the Graph Bandwidth Problem. SWAT 2000: 10-19

Uriel Feige, Marek Karpinski, Michael Langberg: Improved Approximation of MAX-CUT on Graphs of Bounded Degree. Electronic Colloquium on Computational Complexity (ECCC) 7(21) (2000)

Uriel Feige, Marek Karpinski, Michael Langberg: A Note on Approximating MAX-BISECTION on Regular Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(43) (2000)

Uriel Feige, Dror Lapidot, Adi Shamir: Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29(1): 1-28 (1999)

Uriel Feige: Noncryptographic Selection Protocols. FOCS 1999: 142-153

Uriel Feige: Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example. RANDOM-APPROX 1999: 189-196

Uriel Feige: Nonmonotonic Phenomena in Packet Routing. STOC 1999: 583-591

Uriel Feige: A Threshold of ln n for Approximating Set Cover. J. ACM 45(4): 634-652 (1998)

Uriel Feige, Joe Kilian: Zero Knowledge and the Chromatic Number. J. Comput. Syst. Sci. 57(2): 187-199 (1998)

Uriel Feige, Joe Kilian: Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. FOCS 1998: 674-683

Uriel Feige: Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). STOC 1998: 90-99

Uriel Feige, Christian Scheideler: Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). STOC 1998: 624-633

Uriel Feige, Carsten Lund: On the Hardness of Computing the Permanent of Random Matrices. Computational Complexity 6(2): 101-132 (1997)

Uriel Feige: Collecting Coupons on Trees, and the Cover Time of Random Walks. Computational Complexity 6(4): 341-356 (1997)

Uriel Feige, Joe Kilian: On Limited versus Polynomial Nondeterminism. Chicago J. Theor. Comput. Sci. 1997 (1997)

Uriel Feige: Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion. Combinatorica 17(1): 79-90 (1997)

Uriel Feige: A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity. J. Comput. Syst. Sci. 54(2): 305-316 (1997)

Uriel Feige, Giora Rayzman: On the Drift of Short Schedules. CIAC 1997: 74-85

Uriel Feige, Robert Krauthgamer: Stereoscopic families of permutations, and their applications. ISTCS 1997: 85-95

Uriel Feige, Joe Kilian: Making Games Short (Extended Abstract). STOC 1997: 506-516

Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy: Interactive Proofs and the Hardness of Approximating Cliques. J. ACM 43(2): 268-292 (1996)

Greg Barnes, Uriel Feige: Short Random Walks on Graphs. SIAM J. Discrete Math. 9(1): 19-28 (1996)

Don Coppersmith, Uriel Feige, James B. Shearer: Random Walks on Regular and Irregular Graphs. SIAM J. Discrete Math. 9(2): 301-308 (1996)

Uriel Feige: A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. Theor. Comput. Sci. 169(2): 147-160 (1996)

Uriel Feige, Oleg Verbitsky: Error Reduction by Parallel Repetition - a Negative Result. IEEE Conference on Computational Complexity 1996: 70-76

Uriel Feige, Joe Kilian: Zero Knowledge and the Chromatic Number. IEEE Conference on Computational Complexity 1996: 278-287

Uriel Feige, Yuri Rabinovich: Deterministic Approximation of the Cover Time. ISTCS 1996: 208-218

Uriel Feige: A Threshold of ln n for Approximating Set Cover (Preliminary Version). STOC 1996: 314-318

Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor: Adaptively Secure Multi-Party Computation. STOC 1996: 639-648

Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. Computational Complexity 5(1): 60-75 (1995)

Uriel Feige: A Tight Upper Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms 6(1): 51-54 (1995)

Uriel Feige: A Tight Lower Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms 6(4): 433-438 (1995)

Uriel Feige: Observations on Hot Potato Routing. ISTCS 1995: 30-39

Uriel Feige, Michel X. Goemans: Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. ISTCS 1995: 182-189

Mihir Bellare, Uriel Feige, Joe Kilian: On the Role of Shared Randomness in Two Prover Proof Systems. ISTCS 1995: 199-208

Uriel Feige, Joe Kilian: Impossibility results for recycling random bits in two-prover proof systems. STOC 1995: 457-468

Uriel Feige: Randomized graph products, chromatic numbers, and Lovasz theta-function. STOC 1995: 635-640

Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal: Computing with Noisy Information. SIAM J. Comput. 23(5): 1001-1018 (1994)

Yonatan Aumann, Judit Bar-Ilan, Uriel Feige: On the Cost of Recomputing: Tight Bounds on Pebbling with Faults. ICALP 1994: 47-58

Uriel Feige: A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. ICALP 1994: 499-507

Uriel Feige, Joe Kilian: Two prover protocols: low error at affordable rates. STOC 1994: 172-183

Uriel Feige, Joe Kilian, Moni Naor: A minimal model for secure computation (extended abstract). STOC 1994: 554-563

Yonatan Aumann, Uriel Feige: On Message Proof Systems with Known Space Verifiers. CRYPTO 1993: 85-99

Uriel Feige: A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON. FOCS 1993: 238-246

Greg Barnes, Uriel Feige: Short random walks on graphs. STOC 1993: 728-737

Uriel Feige: On the Complexity of Finite Random Functions. Inf. Process. Lett. 44(6): 295-296 (1992)

Uriel Feige, Adi Shamir: Multi-Oracle Interactive Protocols with Constant Space Verifiers. J. Comput. Syst. Sci. 44(2): 259-271 (1992)

Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra: Low Communication 2-Prover Zero-Knowledge Proofs for NP. CRYPTO 1992: 215-227

Uriel Feige, Prabhakar Raghavan: Exact Analysis of Hot-Potato Routing (Extended Abstract). FOCS 1992: 553-562

Uriel Feige, Carsten Lund: On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract). STOC 1992: 643-654

Uriel Feige, László Lovász: Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract). STOC 1992: 733-744

Uriel Feige: On the Success Probability of the Two Provers in One-Round Proof Systems. Structure in Complexity Theory Conference 1991: 116-123

Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy: Approximating Clique is Almost NP-Complete (Preliminary Version). FOCS 1991: 2-12

Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal: Randomized Broadcast in Networks. Random Struct. Algorithms 1(4): 447-460 (1990)

Uriel Feige, Dror Lapidot, Adi Shamir: Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract). FOCS 1990: 308-317

Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal: Randomized Broadcast in Networks. SIGAL International Symposium on Algorithms 1990: 128-137

Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal: Computing with Unreliable Information (Preliminary Version). STOC 1990: 128-137

Uriel Feige, Adi Shamir: Witness Indistinguishable and Witness Hiding Protocols. STOC 1990: 416-426

Uriel Feige, Adi Shamir: Multi-Oracle Interactive Protocols with Space Bounded Verifiers. Structure in Complexity Theory Conference 1989: 158-164

Uriel Feige, Adi Shamir: Zero Knowledge Proofs of Knowledge in Two Rounds. CRYPTO 1989: 526-544

Uriel Feige, Amos Fiat, Adi Shamir: Zero-Knowledge Proofs of Identity. J. Cryptology 1(2): 77-94 (1988)

Uriel Feige, Adi Shamir, Moshe Tennenholtz: The Noisy Oracle Problem. CRYPTO 1988: 284-296

Uriel Feige, Amos Fiat, Adi Shamir: Zero Knowledge Proofs of Identity. STOC 1987: 210-217