The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Uriel Feige: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  129. Santa Claus Meets Hypergraph Matchings. [Citation Graph (, )][DBLP]


  130. PASS Approximation. [Citation Graph (, )][DBLP]


  131. Edge Coloring and Decompositions of Weighted Graphs. [Citation Graph (, )][DBLP]


  132. Refuting Smoothed 3CNF Formulas. [Citation Graph (, )][DBLP]


  133. Maximizing Non-Monotone Submodular Functions. [Citation Graph (, )][DBLP]


  134. On Estimation Algorithms vs Approximation Algorithms. [Citation Graph (, )][DBLP]


  135. On allocations that maximize fairness. [Citation Graph (, )][DBLP]


  136. On smoothed k-CNF formulas and the Walksat algorithm. [Citation Graph (, )][DBLP]


  137. On the power of two, three and four probes. [Citation Graph (, )][DBLP]


  138. Buffer management for colored packets with deadlines. [Citation Graph (, )][DBLP]


  139. Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. [Citation Graph (, )][DBLP]


  140. A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. [Citation Graph (, )][DBLP]


  141. A combinatorial allocation mechanism with penalties for banner advertising. [Citation Graph (, )][DBLP]


  142. Trust-based recommendation systems: an axiomatic approach. [Citation Graph (, )][DBLP]


  143. Approximating the Bandwidth of Caterpillars. [Citation Graph (, )][DBLP]


  144. Interchanging distance and capacity in probabilistic mappings [Citation Graph (, )][DBLP]


  145. Deterministic approximation for the cover time of trees [Citation Graph (, )][DBLP]


  146. Faster FAST(Feedback Arc Set in Tournaments) [Citation Graph (, )][DBLP]


  147. Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph [Citation Graph (, )][DBLP]


  148. A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium [Citation Graph (, )][DBLP]


  149. Understanding Parallel Repetition Requires Understanding Foams. [Citation Graph (, )][DBLP]


  150. Random 3CNF formulas elude the Lovasz theta function. [Citation Graph (, )][DBLP]


Search in 0.009secs, Finished in 0.013secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002