Uriel Feige | Academic Influence

Uriel Feige's AcademicInfluence.com Rankings

Uriel Feige

Computer Science

#1215

World Rank

#1255

Historical Rank

computer-science Degrees

Uriel Feige

Mathematics

#1159

World Rank

#1950

Historical Rank

Complexity Theory

#8

World Rank

#8

Historical Rank

Measure Theory

#581

World Rank

#811

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Uriel Feige's Degrees

PhD Computer Science Weizmann Institute of Science

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Uriel Feige Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Uriel Feige is an Israeli computer scientist who was a doctoral student of Adi Shamir. Life Uriel Feige currently holds the post of Professor at the Department of Computer Science and Applied Mathematics, the Weizmann Institute of Science, Rehovot in Israel.

(See a Problem?)

Uriel Feige's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A threshold of ln n for approximating set cover (1998) (3305)
Spectral graph theory (2019) (2118)
Zero-knowledge proofs of identity (1988) (822)
Maximizing Non-Monotone Submodular Functions (2007) (629)
Witness indistinguishable and witness hiding protocols (1990) (600)
The Dense k -Subgraph Problem (2001) (549)
Adaptively secure multi-party computation (1996) (530)
Interactive proofs and the hardness of approximating cliques (1996) (465)
Zero knowledge and the chromatic number (1996) (458)
Relations between average case complexity and approximation complexity (2002) (380)
Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT (1995) (356)
Detecting high log-densities: an O(n¼) approximation for densest k-subgraph (2010) (324)
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions (1999) (308)
Computing with Noisy Information (1994) (294)
Zero Knowledge Proofs of Knowledge in Two Rounds (1989) (291)
On maximizing welfare when utility functions are subadditive (2006) (283)
Randomized Broadcast in Networks (1990) (271)
Improved approximation algorithms for minimum-weight vertex separators (2005) (271)
Multiple non-interactive zero knowledge proofs based on a single random string (1990) (263)
Spectral techniques applied to sparse random graphs (2005) (261)
Two-prover one-round proof systems: their power and their problems (extended abstract) (1992) (248)
Trust-based recommendation systems: an axiomatic approach (2008) (243)
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e (2006) (219)
A threshold of ln n for approximating set cover (preliminary version) (1996) (219)
A minimal model for secure computation (extended abstract) (1994) (217)
Finding and certifying a large hidden clique in a semirandom graph (2000) (215)
Approximating the domatic number (2000) (210)
A polylogarithmic approximation of the minimum bisection (2000) (206)
A Tight Lower Bound on the Cover Time for Random Walks on Graphs (1995) (206)
Zero knowledge proofs of identity (1987) (174)
A Tight Upper Bound on the Cover Time for Random Walks on Graphs (1995) (172)
Heuristics for Semirandom Graph Problems (2001) (163)
Approximating Min Sum Set Cover (2004) (158)
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning (2001) (157)
Combination can be hard: approximability of the unique coverage problem (2006) (151)
Approximating Maximum Clique by Removing Subgraphs (2005) (149)
Approximating the Bandwidth via Volume Respecting Embeddings (2000) (145)
Genomic Variability within an Organism Exposes Its Cell Lineage Tree (2005) (138)
On the optimality of the random hyperplane rounding technique for MAX CUT (2002) (134)
A Minimal Model for Secure Computation (2002) (117)
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph (2004) (117)
Derandomized graph products (1995) (115)
Exact analysis of hot-potato routing (1992) (110)
On the densest k-subgraph problems (1997) (100)
Noncryptographic selection protocols (1999) (97)
On the success probability of the two provers in one-round proof systems (1991) (94)
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set (2003) (94)
Robust Combinatorial Optimization with Exponential Scenarios (2007) (91)
On the Densest K-subgraph Problem (1997) (90)
Santa claus meets hypergraph matchings (2008) (90)
The RPR2 rounding technique for semidefinite programs (2001) (86)
On allocations that maximize fairness (2008) (86)
Finding hidden cliques in linear time (2009) (84)
An improved approximation ratio for the minimum linear arrangement problem (2007) (80)
The Submodular Welfare Problem with Demand Queries (2010) (75)
Randomized graph products, chromatic numbers, and the Lovász ϑ-function (1997) (75)
Short random walks on graphs (1993) (74)
Making games short (extended abstract) (1997) (74)
Hardness of approximation of the Balanced Complete Bipartite Subgraph problem (2004) (74)
Improved Approximation Algorithms for Minimum Weight Vertex Separators (2008) (73)
Computing with unreliable information (1990) (71)
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs (2007) (70)
Two-Prover Protocols - Low Error at Affordable Rates (2000) (67)
Easily refutable subformulas of large random 3CNF formulas (2004) (64)
Improved approximation of Max-Cut on graphs of bounded degree (2002) (64)
Min-max Graph Partitioning and Small Set Expansion (2011) (62)
On the hardness of computing the permanent of random matrices (1996) (62)
Randomized graph products, chromatic numbers, and Lovasz j-function (1995) (61)
Understanding Parallel Repetition Requires Understanding Foams (2007) (60)
Random Walks on Regular and Irregular Graphs (1996) (60)
Welfare maximization and the supermodular degree (2013) (59)
Witnesses for non-satisfiability of dense random 3CNF formulas (2006) (58)
The inapproximability of lattice and coding problems with preprocessing (2002) (57)
Finding small balanced separators (2006) (57)
Learning and inference in the presence of corrupted inputs (2015) (56)
Error Reduction by Parallel Repetition—A Negative Result (1996) (55)
Contagious Sets in Expanders (2013) (54)
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (2007) (52)
A Unifying Hierarchy of Valuations with Complements and Substitutes (2014) (51)
On Limited versus Polynomial Nondeterminism (1997) (50)
Coping with the NP-Hardness of the Graph Bandwidth Problem (2000) (49)
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph (2006) (48)
Two prover protocols: low error at affordable rates (1994) (48)
Low Communication 2-Prover Zero-Knowledge Proofs for NP (1992) (47)
Making Games Short (2006) (43)
Graphs with tiny vector chromatic numbers and huge chromatic numbers (2002) (41)
Improved Bounds for Acyclic Job Shop Scheduling (2002) (41)
Fair and Truthful Mechanisms for Dichotomous Valuations (2020) (41)
Impossibility results for recycling random bits in two-prover proof systems (1995) (41)
A combinatorial allocation mechanism with penalties for banner advertising (2008) (40)
Approximating Maximum Edge Coloring in Multigraphs (2002) (40)
On the power of two, three and four probes (2009) (39)
Refuting Smoothed 3CNF Formulas (2007) (36)
On the Competitive Ratio of the Random Sampling Auction (2005) (35)
The Noisy Oracle Problem (1988) (35)
Finding OR in a noisy broadcast network (2000) (35)
On Systems of Linear Equations with Two Variables per Equation (2004) (34)
Heuristics for finding large independent sets, with applications to coloring semi-random graphs (1998) (33)
Faster FAST(Feedback Arc Set in Tournaments) (2009) (32)
Approximating the bandwidth via volume respecting embeddings (extended abstract) (1998) (31)
A note on approximating Max-Bisection on regular graphs (2001) (30)
Error reduction by parallel repetition-the state of the art (1995) (29)
Contagious Sets in Random Graphs (2016) (29)
A tight negative example for MMS fair allocations (2021) (28)
Min-Max Graph Partitioning and Small Set Expansion (2014) (27)
Approximating the minimum bisection size (extended abstract) (2000) (27)
Fair-Share Allocations for Agents with Arbitrary Entitlements (2021) (26)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems (2006) (25)
Approximating the Bandwidth of Caterpillars (2005) (25)
On Cutting a Few Vertices from a Graph (2003) (24)
Multi-Oracle Interactive Protocols with Constant Space Verifiers (1992) (24)
Approximating Min-sum Set Cover (2002) (24)
A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity (1997) (23)
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity (1996) (23)
Hardness results for approximating the bandwidth (2011) (23)
Mechanism design with uncertain inputs: (to err is human, to forgive divine) (2011) (22)
Collecting coupons on trees, and the cover time of random walks (1996) (21)
Interchanging distance and capacity in probabilistic mappings (2009) (20)
A local search algorithm for 3SAT (2004) (20)
On smoothed k-CNF formulas and the Walksat algorithm (2009) (19)
Random 3CNF formulas elude the Lovasz theta function (2006) (19)
Observations on hot potato routing (1995) (18)
On the integrality ratio of semidefinite relaxations of MAX CUT (2001) (18)
Collecting Coupons on Trees, and the Analysis of Random Walks (1993) (18)
Oblivious Algorithms for the Maximum Directed Cut Problem (2010) (17)
Short tandem repeat stutter model inferred from direct measurement of in vitro stutter noise (2019) (16)
Multi-oracle interactive protocols with space bounded verifiers (1989) (16)
Heuristic for maximizing DNA reuse in synthetic DNA library assembly. (2014) (16)
Improved bounds for acyclic job shop scheduling (extended abstract) (1998) (15)
Sequential decision making with vector outcomes (2014) (15)
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time (2018) (15)
On the hardness of approximating Max-Satisfy (2006) (14)
Oblivious Rounding and the Integrality Gap (2016) (14)
Responsive Lotteries (2010) (14)
Shotgun assembly of random jigsaw puzzles (2016) (14)
PASS Approximation: A Framework for Analyzing and Designing Heuristics (2013) (14)
On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract) (1992) (14)
Nonmonotonic phenomena in packet routing (1999) (13)
On the complexity of finding balanced oneway cuts (2003) (13)
Best-of-Both-Worlds Fair-Share Allocations (2021) (12)
The Hardness of Approximating Hereditary Properties (2005) (12)
Robust Inference for Multiclass Classification (2018) (12)
On Optimal Strategies for a Hat Game on Graphs (2010) (12)
Deterministic approximation of the cover time (2003) (12)
NP-hardness of hypercube 2-segmentation (2014) (11)
On Estimation Algorithms vs Approximation Algorithms (2008) (11)
Separation between Estimation and Approximation (2015) (11)
The Pcp Theorem and Hardness of Approximation (2003) (11)
On the hardness of approximating N P witnesses (2000) (10)
Universal Factor Graphs (2012) (10)
The allocation problem with submodular utility functions (preliminary version) (2006) (10)
PASS Approximation (2009) (10)
Small Linear Dependencies for Binary Vectors of Low Weight (2008) (10)
On the role of shared randomness in two prover proof systems (1995) (10)
Quantitative Group Testing and the rank of random matrices (2020) (9)
Short Tours through Large Linear Forests (2014) (9)
Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example (1999) (9)
Algorithmic Game Theory - handout 11 and 12 (2013) (9)
Demand Queries with Preprocessing (2014) (9)
On the effect of randomness on planted 3-coloring models (2016) (9)
Finding a Maximum Independent Set in a Sparse Random Graph (2005) (9)
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 (2007) (9)
Finding cliques using few probes (2018) (9)
A randomized time-space tradeoff of O/spl tilde/(mR/spl circ/) for USTCON (1993) (9)
Fair Allocations for Smoothed Utilities (2022) (8)
Chasing Ghosts: Competing with Stateful Policies (2014) (8)
Max-min greedy matching (2018) (8)
Buffer Management for Colored Packets with Deadlines (2009) (8)
Approximation thresholds for combinatorial optimization problems (2003) (8)
Tighter bounds for online bipartite matching (2018) (8)
On Message Proof Systems with Known Space Verifiers (1993) (8)
Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time (2017) (8)
On the Probe Complexity of Local Computation Algorithms (2017) (8)
Edge Coloring and Decompositions of Weighted Graphs (2008) (8)
Improved Bounds for Acyclic Job Shop Scheduling ( Technical Report ) (1998) (7)
Balanced coloring of bipartite graphs (2010) (7)
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium (2010) (7)
A greedy approximation algorithm for minimum-gap scheduling (2013) (7)
An O(n log n) Algorithm for a Load Balancing Problem on Paths (2011) (6)
Deterministic approximation for the cover time of trees (2009) (6)
On the Complexity of Finite Random Functions (1992) (6)
Improved Approximation for Min-Sum Vertex Cover (2006) (6)
A Combinatorial Allocation Mechanism for Banner Advertisement with Penalties (2008) (6)
Oblivious Collaboration (2011) (5)
Feedback Vertex Set (2019) (5)
Rigorous analysis of heuristics for NP-hard problems (2005) (5)
Networks on which hot-potato routing does not livelock (2000) (5)
Recoverable values for independent sets (2011) (5)
The Simplex Algorithm (2020) (5)
Min-Wise versus linear independence (extended abstract) (2000) (5)
Approximate modularity revisited (2016) (5)
A randomized strategy in the mirror game (2019) (5)
Stereoscopic families of permutations, and their applications (1997) (4)
On fair division of a homogeneous good (2014) (4)
Computing with Unreliable Information (Preliminary Version) (1990) (4)
On the Work Function Algorithm for two state task (2007) (4)
Generalized Girth Problems in Graphs and Hypergraphs (2013) (4)
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas (2009) (4)
Improved maximin fair allocation of indivisible items to three agents (2022) (4)
Random walks with the minimum degree local rule have $O(n^2)$ cover time (2016) (3)
A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON (1993) (3)
Navigating in Trees with Permanently Noisy Advice (2021) (3)
On giant components and treewidth in the layers model (2014) (3)
A polylogarithmic approximation of the minimum bisection (Extended Abstract) (2000) (3)
Exact Analysis of Hot-Potato Routing (Extended Abstract) (1992) (3)
Why are Images Smooth? (2014) (3)
Target Set Selection for Conservative Populations (2019) (3)
Are Gross Substitutes a Substitute for Submodular Valuations? (2021) (3)
On Estimation Algorithms versus Approximation Algorithms (2008) (2)
Optimization with Uniform Size Queries (2017) (2)
Sampling Vertex Degrees and Estimating Network Load Parameters (2003) (2)
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms (2016) (2)
The Cascade Auction - A Mechanism for Deterring Collusion in Auctions (2013) (2)
Approximating Clique is Almost NP-Complete (Preliminary Version) (1991) (2)
Fair Shares: Feasibility, Domination and Incentives (2022) (2)
A tight bound for the clique query problem in two rounds (2021) (1)
Noncryptographic Selection Protocols ( Extended Abstract ) (1999) (1)
Planted Random 3 SAT with a Small Fraction of 1-Clauses (2012) (1)
On the drift of short schedules (1997) (1)
On the sum of nonnegative independentrandom variables with unbounded varianceUriel (1)
Approximating the Bandwidth via Volume Respecting Embeddings (Preliminary Version 3) (1998) (1)
Improved approximation of the minimum cover time (2005) (1)
On Expected Polynomial Time Simulation of Zero Knowledge Protocols (1989) (1)
The Ordered Covering Problem (2018) (1)
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees (2008) (1)
On the cost of recomputing: Tight bounds on pebbling with faults (1994) (1)
On picking sequences for chores (2022) (1)
Introduction to Semirandom Models (2020) (1)
Improved Performance Guarantees for BandwidthMinimization Heuristics ( draft ) (1998) (1)
Mastering multi-player games (2012) (1)
The Weizmann Workshop on Probabilistic Proof Systems (1994) (1)
Maximin fair allocations with two item values (2022) (1)
PASS Approximation: A Framework for Analyzing and Designing Heuristics (2012) (1)
Musical Chairs (2012) (1)
Short Tandem Repeat stutter_model_inferred from direct measurement of in vitro stutter noise (2016) (1)
SPECIAL SECTION ON CONSTRAINT SATISFACTION PROBLEMS AND MESSAGE PASSING ALGORITHMS (2011) (0)
A New Approach to Fair Distribution of Welfare (2019) (0)
Lecture 1 – Sorting and Selection (2014) (0)
On allocations that give intersecting groups their fair share (2022) (0)
Optimization with Uniform Size Queries (2016) (0)
Lectures 4 and 5 – Matchings (2014) (0)
On the path partition number of 6‐regular graphs (2019) (0)
D S ] 2 9 M ar 2 01 8 Approximate Modularity Revisited ∗ (2018) (0)
The permanent and the determinant (2022) (0)
Finding a semi-randomly hidden clique (2021) (0)
Approximate Modularity Revisited | SIAM Journal on Computing | Vol. 49, No. 1 | Society for Industrial and Applied Mathematics (2020) (0)
Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008: Preface (2008) (0)
Invitation games and the price of stability (2014) (0)
Contests for Revenue Share∗ (2016) (0)
Lecture 10 – Algorithmic version of the local lemma (2014) (0)
Algorithmic version of the local lemma (2010) (0)
TheBestNurturers in Computer Science Research (2005) (0)
Deterministic approximation of the cover time ( Preliminary version ) (2007) (0)
On the diversity principle and local falsifiability (2012) (0)
Algorithms for Computing Solution Concepts in Game Theory (2008) (0)
On Fair Allocation of Indivisible Goods to Submodular Agents (2023) (0)
Lecture 1The Basics of Linear Programming (2011) (0)
Algorithmic Game Theory - handout2 (2008) (0)
Minimizing regret in repeated play of games (2013) (0)
Fair allocation and linear programming (2022) (0)
How to hide a clique? (2020) (0)
Lecture 12 – The permanent and the determinant (2014) (0)
A Final Assignment: (2019) (0)
Metric facility location (2019) (0)
The Ordered Covering Problem (2017) (0)
Smoothed analysis for the knapsack problem (2021) (0)
Introduction to spectral graph theory (2022) (0)
Oblivious Algorithms for the Maximum Directed Cut Problem (2013) (0)
Exponential time algorithms for graph coloring (2011) (0)
Dynamic programming, treewidth and graph minors (2022) (0)
A greedy approximation algorithm for minimum-gap scheduling (2016) (0)
Session details: Session 2A (2007) (0)
November 2011 1 The Ellipsoid Algorithm (2011) (0)
On the Profile of Multiplicities of Complete Subgraphs (2017) (0)
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241) (2011) (0)
Lectures 8 and 9 – Spectral graph theory (2014) (0)
On robustly asymmetric graphs (2014) (0)
26 11241 – Design and Analysis of Randomized and Approximation Algorithms 2 Table of Contents Executive Summary (2011) (0)
Competition among asymmetric sellers with fixed supply (2013) (0)
Connectivity of Random High Dimensional Geometric Graphs (2013) (0)
Lecture on Spectral graph theory (2021) (0)
Lectures 6 , 7 beginning of 8 – Treewidth and graph minors (2014) (0)
Smoothed analysis for the subset sum and knapsack problems (2022) (0)

This paper list is powered by the following services:

Other Resources About Uriel Feige

en.wikipedia.org

What Schools Are Affiliated With Uriel Feige?

Uriel Feige is affiliated with the following schools: