| 2009 |
|---|
| 146 | EE | Noga Alon,
Uriel Feige:
On the power of two, three and four probes.
SODA 2009: 346-354 |
| 145 | EE | 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 |
| 2008 |
|---|
| 144 | EE | Arash Asadpour,
Uriel Feige,
Amin Saberi:
Santa Claus Meets Hypergraph Matchings.
APPROX-RANDOM 2008: 10-20 |
| 143 | EE | Uriel Feige,
Mohit Singh:
Edge Coloring and Decompositions of Weighted Graphs.
ESA 2008: 405-416 |
| 142 | EE | Uriel Feige:
On Estimation Algorithms vs Approximation Algorithms.
FSTTCS 2008 |
| 141 | EE | Uriel Feige:
On allocations that maximize fairness.
SODA 2008: 287-293 |
| 140 | EE | Yossi Azar,
Uriel Feige,
Daniel Glasner:
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.
SWAT 2008: 319-330 |
| 139 | EE | Uriel Feige,
Nicole Immorlica,
Vahab S. Mirrokni,
Hamid Nazerzadeh:
A combinatorial allocation mechanism with penalties for banner advertising.
WWW 2008: 169-178 |
| 138 | EE | 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 |
| 137 | EE | Uriel Feige,
MohammadTaghi Hajiaghayi,
James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators.
SIAM J. Comput. 38(2): 629-657 (2008) |
| 136 | EE | 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) |
| 135 | EE | Uriel Feige,
Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph.
SIAM J. Discrete Math. 22(2): 693-718 (2008) |
| 2007 |
|---|
| 134 | | David S. Johnson,
Uriel Feige:
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007
ACM 2007 |
| 133 | EE | Uriel Feige,
Mohit Singh:
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs.
APPROX-RANDOM 2007: 104-118 |
| 132 | EE | Uriel Feige:
Refuting Smoothed 3CNF Formulas.
FOCS 2007: 407-417 |
| 131 | EE | Uriel Feige,
Vahab S. Mirrokni,
Jan Vondrák:
Maximizing Non-Monotone Submodular Functions.
FOCS 2007: 461-471 |
| 130 | EE | Uriel Feige,
Guy Kindler,
Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
IEEE Conference on Computational Complexity 2007: 179-192 |
| 129 | EE | Uriel Feige,
Kamal Jain,
Mohammad Mahdian,
Vahab S. Mirrokni:
Robust Combinatorial Optimization with Exponential Scenarios.
IPCO 2007: 439-453 |
| 128 | EE | Uriel Feige,
Guy Kindler,
Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
Electronic Colloquium on Computational Complexity (ECCC) 14(043): (2007) |
| 127 | EE | Uriel Feige,
James R. Lee:
An improved approximation ratio for the minimum linear arrangement problem.
Inf. Process. Lett. 101(1): 26-29 (2007) |
| 126 | EE | Uriel Feige,
Eran Ofek:
Easily refutable subformulas of large random 3CNF formulas.
Theory of Computing 3(1): 25-43 (2007) |
| 2006 |
|---|
| 125 | EE | Uriel Feige,
Elchanan Mossel,
Dan Vilenchik:
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
APPROX-RANDOM 2006: 339-350 |
| 124 | EE | Uriel Feige,
Jeong Han Kim,
Eran Ofek:
Witnesses for non-satisfiability of dense random 3CNF formulas.
FOCS 2006: 497-508 |
| 123 | EE | Uriel Feige,
Jan Vondrák:
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.
FOCS 2006: 667-676 |
| 122 | EE | 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 |
| 121 | EE | Uriel Feige,
Mohammad Mahdian:
Finding small balanced separators.
STOC 2006: 375-384 |
| 120 | EE | Uriel Feige:
On maximizing welfare when utility functions are subadditive.
STOC 2006: 41-50 |
| 119 | EE | Uriel Feige,
Eran Ofek:
Random 3CNF formulas elude the Lovasz theta function
CoRR abs/cs/0603084: (2006) |
| 118 | EE | Eran Ofek,
Uriel Feige:
Random 3CNF formulas elude the Lovasz theta function.
Electronic Colloquium on Computational Complexity (ECCC) 13(043): (2006) |
| 117 | EE | Uriel Feige,
Daniel Reichman:
On the hardness of approximating Max-Satisfy.
Inf. Process. Lett. 97(1): 31-35 (2006) |
| 116 | EE | Uriel Feige,
Michael Langberg:
The RPR2 rounding technique for semidefinite programs.
J. Algorithms 60(1): 1-23 (2006) |
| 115 | EE | 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) |
| 2005 |
|---|
| 114 | EE | Uriel Feige,
Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph.
APPROX-RANDOM 2005: 282-293 |
| 113 | EE | Uriel Feige,
Kunal Talwar:
Approximating the Bandwidth of Caterpillars.
APPROX-RANDOM 2005: 62-73 |
| 112 | EE | Uriel Feige:
Rigorous analysis of heuristics for NP-hard problems.
SODA 2005: 927 |
| 111 | EE | Uriel Feige,
Mohammad Taghi Hajiaghayi,
James R. Lee:
Improved approximation algorithms for minimum-weight vertex separators.
STOC 2005: 563-572 |
| 110 | EE | Uriel Feige,
Abraham Flaxman,
Jason D. Hartline,
Robert D. Kleinberg:
On the Competitive Ratio of the Random Sampling Auction.
WINE 2005: 878-886 |
| 109 | EE | Uriel Feige,
Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph
Electronic Colloquium on Computational Complexity (ECCC)(050): (2005) |
| 108 | EE | Uriel Feige,
Eran Ofek:
Spectral techniques applied to sparse random graphs.
Random Struct. Algorithms 27(2): 251-275 (2005) |
| 107 | EE | Eden Chlamtac,
Uriel Feige:
Improved approximation of the minimum cover time.
Theor. Comput. Sci. 341(1-3): 22-38 (2005) |
| 2004 |
|---|
| 106 | EE | Uriel Feige,
Daniel Reichman:
On Systems of Linear Equations with Two Variables per Equation.
APPROX-RANDOM 2004: 117-127 |
| 105 | EE | Uriel Feige,
Eran Ofek:
Easily Refutable Subformulas of Large Random 3CNF Formulas.
ICALP 2004: 519-530 |
| 104 | EE | Uriel Feige:
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph.
STOC 2004: 594-603 |
| 103 | EE | Uriel Feige,
László Lovász,
Prasad Tetali:
Approximating Min Sum Set Cover.
Algorithmica 40(4): 219-234 (2004) |
| 102 | EE | Uriel Feige,
Daniel Reichman:
On The Hardness of Approximating Max-Satisfy
Electronic Colloquium on Computational Complexity (ECCC)(119): (2004) |
| 101 | EE | Uriel Feige,
Daniele Micciancio:
The inapproximability of lattice and coding problems with preprocessing.
J. Comput. Syst. Sci. 69(1): 45-67 (2004) |
| 100 | EE | Uriel Feige,
Michael Langberg,
Gideon Schechtman:
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
SIAM J. Comput. 33(6): 1338-1368 (2004) |
| 99 | EE | Uriel Feige:
Approximating Maximum Clique by Removing Subgraphs.
SIAM J. Discrete Math. 18(2): 219-225 (2004) |
| 2003 |
|---|
| 98 | EE | Uriel Feige:
Approximation thresholds for combinatorial optimization problems
CoRR cs.CC/0304039: (2003) |
| 97 | EE | Uriel Feige,
Robert Krauthgamer,
Kobbi Nissim:
On Cutting a Few Vertices from a Graph.
Discrete Applied Mathematics 127(3): 643-649 (2003) |
| 96 | EE | Uriel Feige,
Orly Yahalom:
On the complexity of finding balanced oneway cuts.
Inf. Process. Lett. 87(1): 1-5 (2003) |
| 95 | EE | Uriel Feige,
Yuri Rabinovich:
Deterministic approximation of the cover time.
Random Struct. Algorithms 23(1): 1-22 (2003) |
| 94 | EE | 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) |
| 2002 |
|---|
| 93 | EE | Uriel Feige,
Eran Ofek,
Udi Wieder:
Approximating Maximum Edge Coloring in Multigraphs.
APPROX 2002: 108-121 |
| 92 | EE | Uriel Feige,
László Lovász,
Prasad Tetali:
Approximating Min-sum Set Cover.
APPROX 2002: 94-107 |
| 91 | EE | Uriel Feige,
Michael Langberg,
Gideon Schechtman:
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
FOCS 2002: 283-292 |
| 90 | EE | Uriel Feige,
Daniele Micciancio:
The Inapproximability of Lattice and Coding Problems with Preprocessing.
IEEE Conference on Computational Complexity 2002: 44-52 |
| 89 | EE | Uriel Feige:
Relations between Average Case Complexity and Approximation Complexity.
IEEE Conference on Computational Complexity 2002: 5 |
| 88 | EE | Uriel Feige:
Relations between average case complexity and approximation complexity.
STOC 2002: 534-543 |
| 87 | EE | Uriel Feige,
Christian Scheideler:
Improved Bounds for Acyclic Job Shop Scheduling.
Combinatorica 22(3): 361-399 (2002) |
| 86 | EE | Uriel Feige,
Oleg Verbitsky:
Error Reduction by Parallel Repetition - A Negative Result.
Combinatorica 22(4): 461-478 (2002) |
| 85 | EE | Uriel Feige,
Marek Karpinski,
Michael Langberg:
Improved approximation of Max-Cut on graphs of bounded degree.
J. Algorithms 43(2): 201-219 (2002) |
| 84 | EE | Uriel Feige,
Gideon Schechtman:
On the optimality of the random hyperplane rounding technique for MAX CUT.
Random Struct. Algorithms 20(3): 403-440 (2002) |
| 83 | EE | Uriel Feige,
Robert Krauthgamer:
A Polylogarithmic Approximation of the Minimum Bisection.
SIAM J. Comput. 31(4): 1090-1118 (2002) |
| 82 | EE | Uriel Feige,
Magnús M. Halldórsson,
Guy Kortsarz,
Aravind Srinivasan:
Approximating the Domatic Number.
SIAM J. Comput. 32(1): 172-195 (2002) |
| 81 | | Uriel Feige,
Giora Rayzman:
On the drift of short schedules.
Theor. Comput. Sci. 289(1): 473-484 (2002) |
| 2001 |
|---|
| 80 | EE | Uriel Feige,
Michael Langberg:
The RPR2 Rounding Technique for Semidefinite Programs.
ICALP 2001: 213-224 |
| 79 | EE | Uriel Feige,
Gideon Schechtman:
On the integrality ratio of semidefinite relaxations of MAX CUT.
STOC 2001: 433-442 |
| 78 | EE | Uriel Feige,
David Peleg,
Guy Kortsarz:
The Dense k-Subgraph Problem.
Algorithmica 29(3): 410-421 (2001) |
| 77 | EE | Uriel Feige,
Marek Karpinski,
Michael Langberg:
A note on approximating Max-Bisection on regular graphs.
Inf. Process. Lett. 79(4): 181-188 (2001) |
| 76 | EE | Uriel Feige,
Michael Langberg:
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning.
J. Algorithms 41(2): 174-211 (2001) |
| 75 | EE | Uriel Feige,
Joe Kilian:
Heuristics for Semirandom Graph Problems.
J. Comput. Syst. Sci. 63(4): 639-671 (2001) |
| 2000 |
|---|
| 74 | EE | Uriel Feige,
Michael Langberg,
Kobbi Nissim:
On the hardness of approximating N P witnesses.
APPROX 2000: 120-131 |
| 73 | | Uriel Feige,
Robert Krauthgamer:
A polylogarithmic approximation of the minimum bisection.
FOCS 2000: 105-115 |
| 72 | EE | Andrei Z. Broder,
Uriel Feige:
Min-Wise versus linear independence (extended abstract).
SODA 2000: 147-154 |
| 71 | EE | Uriel Feige,
Magnús M. Halldórsson,
Guy Kortsarz:
Approximating the domatic number.
STOC 2000: 134-143 |
| 70 | EE | Uriel Feige,
Robert Krauthgamer,
Kobbi Nissim:
Approximating the minimum bisection size (extended abstract).
STOC 2000: 530-536 |
| 69 | EE | Uriel Feige:
Coping with the NP-Hardness of the Graph Bandwidth Problem.
SWAT 2000: 10-19 |
| 68 | EE | Uriel Feige,
Robert Krauthgamer:
Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Computing 13(1): 53-58 (2000) |
| 67 | EE | 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) |
| 66 | EE | Uriel Feige,
Marek Karpinski,
Michael Langberg:
A Note on Approximating MAX-BISECTION on Regular Graphs
Electronic Colloquium on Computational Complexity (ECCC) 7(43): (2000) |
| 65 | EE | Uriel Feige,
Joe Kilian:
Finding OR in a noisy broadcast network.
Inf. Process. Lett. 73(1-2): 69-75 (2000) |
| 64 | | Uriel Feige:
Approximating the Bandwidth via Volume Respecting Embeddings.
J. Comput. Syst. Sci. 60(3): 510-539 (2000) |
| 63 | | Uriel Feige,
Robert Krauthgamer:
Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms 16(2): 195-208 (2000) |
| 62 | | Uriel Feige,
Joe Kilian:
Two-Prover Protocols - Low Error at Affordable Rates.
SIAM J. Comput. 30(1): 324-346 (2000) |
| 61 | EE | 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) |
| 1999 |
|---|
| 60 | EE | Uriel Feige:
Noncryptographic Selection Protocols.
FOCS 1999: 142-153 |
| 59 | | Uriel Feige:
Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example.
RANDOM-APPROX 1999: 189-196 |
| 58 | EE | Uriel Feige:
Nonmonotonic Phenomena in Packet Routing.
STOC 1999: 583-591 |
| 57 | | Uriel Feige,
Dror Lapidot,
Adi Shamir:
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.
SIAM J. Comput. 29(1): 1-28 (1999) |
| 1998 |
|---|
| 56 | EE | Uriel Feige,
Joe Kilian:
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.
FOCS 1998: 674-683 |
| 55 | EE | Uriel Feige,
Christian Scheideler:
Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
STOC 1998: 624-633 |
| 54 | EE | Uriel Feige:
Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
STOC 1998: 90-99 |
| 53 | EE | Uriel Feige:
A Threshold of ln n for Approximating Set Cover.
J. ACM 45(4): 634-652 (1998) |
| 52 | | Uriel Feige,
Joe Kilian:
Zero Knowledge and the Chromatic Number.
J. Comput. Syst. Sci. 57(2): 187-199 (1998) |
| 1997 |
|---|
| 51 | | Uriel Feige,
Giora Rayzman:
On the Drift of Short Schedules.
CIAC 1997: 74-85 |
| 50 | EE | Uriel Feige,
Robert Krauthgamer:
Stereoscopic families of permutations, and their applications.
ISTCS 1997: 85-95 |
| 49 | EE | Uriel Feige,
Joe Kilian:
Making Games Short (Extended Abstract).
STOC 1997: 506-516 |
| 48 | EE | Uriel Feige,
Joe Kilian:
On Limited versus Polynomial Nondeterminism.
Chicago J. Theor. Comput. Sci. 1997: (1997) |
| 47 | | Uriel Feige:
Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion.
Combinatorica 17(1): 79-90 (1997) |
| 46 | | Uriel Feige,
Carsten Lund:
On the Hardness of Computing the Permanent of Random Matrices.
Computational Complexity 6(2): 101-132 (1997) |
| 45 | | Uriel Feige:
Collecting Coupons on Trees, and the Cover Time of Random Walks.
Computational Complexity 6(4): 341-356 (1997) |
| 44 | | Uriel Feige:
A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity.
J. Comput. Syst. Sci. 54(2): 305-316 (1997) |
| 1996 |
|---|
| 43 | EE | Uriel Feige,
Joe Kilian:
Zero Knowledge and the Chromatic Number.
IEEE Conference on Computational Complexity 1996: 278-287 |
| 42 | EE | Uriel Feige,
Oleg Verbitsky:
Error Reduction by Parallel Repetition - a Negative Result.
IEEE Conference on Computational Complexity 1996: 70-76 |
| 41 | | Uriel Feige,
Yuri Rabinovich:
Deterministic Approximation of the Cover Time.
ISTCS 1996: 208-218 |
| 40 | EE | Uriel Feige:
A Threshold of ln n for Approximating Set Cover (Preliminary Version).
STOC 1996: 314-318 |
| 39 | EE | Ran Canetti,
Uriel Feige,
Oded Goldreich,
Moni Naor:
Adaptively Secure Multi-Party Computation.
STOC 1996: 639-648 |
| 38 | EE | 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) |
| 37 | EE | Greg Barnes,
Uriel Feige:
Short Random Walks on Graphs.
SIAM J. Discrete Math. 9(1): 19-28 (1996) |
| 36 | EE | Don Coppersmith,
Uriel Feige,
James B. Shearer:
Random Walks on Regular and Irregular Graphs.
SIAM J. Discrete Math. 9(2): 301-308 (1996) |
| 35 | EE | Uriel Feige:
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
Theor. Comput. Sci. 169(2): 147-160 (1996) |
| 1995 |
|---|
| 34 | | 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 |
| 33 | | Mihir Bellare,
Uriel Feige,
Joe Kilian:
On the Role of Shared Randomness in Two Prover Proof Systems.
ISTCS 1995: 199-208 |
| 32 | | Uriel Feige:
Observations on Hot Potato Routing.
ISTCS 1995: 30-39 |
| 31 | EE | Uriel Feige,
Joe Kilian:
Impossibility results for recycling random bits in two-prover proof systems.
STOC 1995: 457-468 |
| 30 | EE | Uriel Feige:
Randomized graph products, chromatic numbers, and Lovasz theta-function.
STOC 1995: 635-640 |
| 29 | | Noga Alon,
Uriel Feige,
Avi Wigderson,
David Zuckerman:
Derandomized Graph Products.
Computational Complexity 5(1): 60-75 (1995) |
| 28 | | Uriel Feige:
A Tight Upper Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms 6(1): 51-54 (1995) |
| 27 | | Uriel Feige:
A Tight Lower Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms 6(4): 433-438 (1995) |
| 1994 |
|---|
| 26 | | Yonatan Aumann,
Judit Bar-Ilan,
Uriel Feige:
On the Cost of Recomputing: Tight Bounds on Pebbling with Faults.
ICALP 1994: 47-58 |
| 25 | | Uriel Feige:
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
ICALP 1994: 499-507 |
| 24 | EE | Uriel Feige,
Joe Kilian:
Two prover protocols: low error at affordable rates.
STOC 1994: 172-183 |
| 23 | EE | Uriel Feige,
Joe Kilian,
Moni Naor:
A minimal model for secure computation (extended abstract).
STOC 1994: 554-563 |
| 22 | | Uriel Feige,
Prabhakar Raghavan,
David Peleg,
Eli Upfal:
Computing with Noisy Information.
SIAM J. Comput. 23(5): 1001-1018 (1994) |
| 1993 |
|---|
| 21 | EE | Yonatan Aumann,
Uriel Feige:
On Message Proof Systems with Known Space Verifiers.
CRYPTO 1993: 85-99 |
| 20 | | Uriel Feige:
A Randomized Time-Space Tradefoff of \tildeO(m\tildeR) for USTCON
FOCS 1993: 238-246 |
| 19 | EE | Greg Barnes,
Uriel Feige:
Short random walks on graphs.
STOC 1993: 728-737 |
| 1992 |
|---|
| 18 | EE | Cynthia Dwork,
Uriel Feige,
Joe Kilian,
Moni Naor,
Shmuel Safra:
Low Communication 2-Prover Zero-Knowledge Proofs for NP.
CRYPTO 1992: 215-227 |
| 17 | | Uriel Feige,
Prabhakar Raghavan:
Exact Analysis of Hot-Potato Routing (Extended Abstract)
FOCS 1992: 553-562 |
| 16 | | Uriel Feige,
Carsten Lund:
On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)
STOC 1992: 643-654 |
| 15 | | Uriel Feige,
László Lovász:
Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)
STOC 1992: 733-744 |
| 14 | | Uriel Feige:
On the Complexity of Finite Random Functions.
Inf. Process. Lett. 44(6): 295-296 (1992) |
| 13 | | Uriel Feige,
Adi Shamir:
Multi-Oracle Interactive Protocols with Constant Space Verifiers.
J. Comput. Syst. Sci. 44(2): 259-271 (1992) |
| 1991 |
|---|
| 12 | | Uriel Feige,
Shafi Goldwasser,
László Lovász,
Shmuel Safra,
Mario Szegedy:
Approximating Clique is Almost NP-Complete (Preliminary Version)
FOCS 1991: 2-12 |
| 11 | | Uriel Feige:
On the Success Probability of the Two Provers in One-Round Proof Systems.
Structure in Complexity Theory Conference 1991: 116-123 |
| 1990 |
|---|
| 10 | | Uriel Feige,
Dror Lapidot,
Adi Shamir:
Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)
FOCS 1990: 308-317 |
| 9 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Randomized Broadcast in Networks.
SIGAL International Symposium on Algorithms 1990: 128-137 |
| 8 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Computing with Unreliable Information (Preliminary Version)
STOC 1990: 128-137 |
| 7 | | Uriel Feige,
Adi Shamir:
Witness Indistinguishable and Witness Hiding Protocols
STOC 1990: 416-426 |
| 6 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Randomized Broadcast in Networks.
Random Struct. Algorithms 1(4): 447-460 (1990) |
| 1989 |
|---|
| 5 | EE | Uriel Feige,
Adi Shamir:
Zero Knowledge Proofs of Knowledge in Two Rounds.
CRYPTO 1989: 526-544 |
| 4 | | Uriel Feige,
Adi Shamir:
Multi-Oracle Interactive Protocols with Space Bounded Verifiers.
Structure in Complexity Theory Conference 1989: 158-164 |
| 1988 |
|---|
| 3 | EE | Uriel Feige,
Adi Shamir,
Moshe Tennenholtz:
The Noisy Oracle Problem.
CRYPTO 1988: 284-296 |
| 2 | | Uriel Feige,
Amos Fiat,
Adi Shamir:
Zero-Knowledge Proofs of Identity.
J. Cryptology 1(2): 77-94 (1988) |
| 1987 |
|---|
| 1 | | Uriel Feige,
Amos Fiat,
Adi Shamir:
Zero Knowledge Proofs of Identity
STOC 1987: 210-217 |
