Person: Uriel Feige

DBLP: Feige:Uriel

Facilitated 1 volumes:

Ed

Contributed to:

2014

2012

2011

2011

2010

2006

2005

2004

2004

2002

2001

2001

2000

1999

1998

1997

1996

1995

1994

1994

1993

1992

1990

1987

Wrote 33 papers:

ICALP-v1-2014-FeigeJ #preprocessor #query

Demand Queries with Preprocessing (UF, SJ), pp. 477–488.

ICALP-v1-2012-FeigeJ #graph

Universal Factor Graphs (UF, SJ), pp. 339–350.

ICALP-v1-2011-FeigeR #independence #set

Recoverable Values for Independent Sets (UF, DR), pp. 486–497.

STOC-2011-FeigeT #design #nondeterminism

Mechanism design with uncertain inputs: (to err is human, to forgive divine) (UF, MT), pp. 549–558.

STOC-2010-BhaskaraCCFV #approximate #detection

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph (AB, MC, EC, UF, AV), pp. 201–210.

STOC-2006-Feige #on the

On maximizing welfare when utility functions are subadditive (UF), pp. 41–50.

STOC-2006-FeigeM

Finding small balanced separators (UF, MM), pp. 375–384.

STOC-2005-FeigeHL #algorithm #approximate

Improved approximation algorithms for minimum-weight vertex separators (UF, MTH, JRL), pp. 563–572.

ICALP-2004-FeigeO #random #scalability

Easily Refutable Subformulas of Large Random 3CNF Formulas (UF, EO), pp. 519–530.

STOC-2004-Feige #bound #graph #independence #on the #random

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph (UF), pp. 594–603.

STOC-2002-Feige #approximate #complexity

Relations between average case complexity and approximation complexity (UF), pp. 534–543.

ICALP-2001-FeigeL #source code

The RPR2 Rounding Technique for Semidefinite Programs (UF, ML), pp. 213–224.

STOC-2001-FeigeS #on the

On the integrality ratio of semidefinite relaxations of MAX CUT (UF, GS), pp. 433–442.

STOC-2000-FeigeHK #approximate

Approximating the domatic number (UF, MMH, GK), pp. 134–143.

STOC-2000-FeigeKN #approximate

Approximating the minimum bisection size (UF, RK, KN), pp. 530–536.

STOC-1999-Feige

Nonmonotonic Phenomena in Packet Routing (UF), pp. 583–591.

STOC-1998-Feige #approximate

Approximating the Bandwidth via Volume Respecting Embeddings (UF), pp. 90–99.

STOC-1998-FeigeS #bound #scheduling

Improved Bounds for Acyclic Job Shop Scheduling (UF, CS), pp. 624–633.

STOC-1997-FeigeK #game studies

Making Games Short (UF, JK), pp. 506–516.

STOC-1996-CanettiFGN #adaptation #multi

Adaptively Secure Multi-Party Computation (RC, UF, OG, MN), pp. 639–648.

STOC-1996-Feige #approximate #set

A Threshold of ln n for Approximating Set Cover (UF), pp. 314–318.

STOC-1995-Feige #graph #random

Randomized graph products, chromatic numbers, and Lovasz theta-function (UF), pp. 635–640.

STOC-1995-FeigeK #proving #random

Impossibility results for recycling random bits in two-prover proof systems (UF, JK), pp. 457–468.

ICALP-1994-AumannBF #bound #cost analysis #fault #on the

On the Cost of Recomputing: Tight Bounds on Pebbling with Faults (YA, JBI, UF), pp. 47–58.

ICALP-1994-Feige #algorithm #graph #performance #random

A Fast Randomized LOGSPACE Algorithm for Graph Connectivity (UF), pp. 499–507.

STOC-1994-FeigeK #fault #protocol #proving

Two prover protocols: low error at affordable rates (UF, JK), pp. 172–183.

STOC-1994-FeigeKN

A minimal model for secure computation (UF, JK, MN), pp. 554–563.

STOC-1993-BarnesF #graph #random

Short random walks on graphs (GB, UF), pp. 728–737.

STOC-1992-FeigeL #matrix #on the #random

On the Hardness of Computing the Permanent of Random Matrices (UF, CL), pp. 643–654.

STOC-1992-FeigeL92a #problem #proving

Two-Prover One-Round Proof Systems: Their Power and Their Problems (UF, LL), pp. 733–744.

STOC-1990-FeigePRU

Computing with Unreliable Information (UF, DP, PR, EU), pp. 128–137.

STOC-1990-FeigeS #protocol

Witness Indistinguishable and Witness Hiding Protocols (UF, AS), pp. 416–426.

STOC-1987-FeigeFS #proving

Zero Knowledge Proofs of Identity (UF, AF, AS), pp. 210–217.