A threshold of ln n for approximating set cover U Feige Journal of the ACM (JACM) 45 (4), 634-652, 1998 | 3767 | 1998 |
Zero knowledge proofs of identity U Fiege, A Fiat, A Shamir Proceedings of the nineteenth annual ACM symposium on Theory of computing …, 1987 | 1961 | 1987 |
Maximizing non-monotone submodular functions U Feige, VS Mirrokni, J Vondrák SIAM Journal on Computing 40 (4), 1133-1153, 2011 | 813 | 2011 |
Witness indistinguishable and witness hiding protocols U Feige, A Shamir Proceedings of the twenty-second annual ACM symposium on Theory of computing …, 1990 | 790 | 1990 |
The Dense k -Subgraph Problem U Feige, D Peleg, G Kortsarz Algorithmica 29, 410-421, 2001 | 738 | 2001 |
Adaptively secure multi-party computation R Canetti, U Feige, O Goldreich, M Naor Proceedings of the twenty-eighth annual ACM symposium on Theory of computing …, 1996 | 738 | 1996 |
Approximating clique is almost NP-complete U Feige, S Goldwasser, L Lovász, S Safra, M Szegedy [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science …, 1991 | 624 | 1991 |
Zero knowledge and the chromatic number U Feige, J Kilian Journal of Computer and System Sciences 57 (2), 187-199, 1998 | 595 | 1998 |
Interactive proofs and the hardness of approximating cliques U Feige, S Goldwasser, L Lovász, S Safra, M Szegedy Journal of the ACM (JACM) 43 (2), 268-292, 1996 | 554 | 1996 |
A threshold of ln n for approximating set cover (preliminary version) U Feige Proceedings of the twenty-eighth annual ACM symposium on Theory of computing …, 1996 | 547 | 1996 |
Relations between average case complexity and approximation complexity U Feige Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 469 | 2002 |
Approximating the value of two power proof systems, with applications to max 2sat and max dicut U Feige, M Goemans Proceedings third Israel symposium on the theory of computing and systems …, 1995 | 467 | 1995 |
Improved approximation algorithms for minimum-weight vertex separators U Feige, MT Hajiaghayi, JR Lee Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005 | 431 | 2005 |
Detecting high log-densities: an O(n¼) approximation for densest k-subgraph A Bhaskara, M Charikar, E Chlamtac, U Feige, A Vijayaraghavan Proceedings of the forty-second ACM symposium on Theory of computing, 201-210, 2010 | 405 | 2010 |
Multiple non-interactive zero knowledge proofs based on a single random string U Feige, D Lapidot, A Shamir Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science …, 1990 | 395 | 1990 |
Multiple noninteractive zero knowledge proofs under general assumptions U Feige, D Lapidot, A Shamir SIAM Journal on computing 29 (1), 1-28, 1999 | 391 | 1999 |
A minimal model for secure computation U Feige, J Killian, M Naor Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994 | 377 | 1994 |
Zero knowledge proofs of knowledge in two rounds U Feige, A Shamir Conference on the Theory and Application of Cryptology, 526-544, 1989 | 360 | 1989 |
On maximizing welfare when utility functions are subadditive U Feige Proceedings of the thirty-eighth annual ACM symposium on Theory of computing …, 2006 | 353 | 2006 |
Computing with noisy information U Feige, P Raghavan, D Peleg, E Upfal SIAM Journal on Computing 23 (5), 1001-1018, 1994 | 353 | 1994 |