- Martin E. Dyer
, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda:
Randomly Coloring Constant Degree Graphs. FOCS 2004: 582-589 - Lisa Fleischer, Kamal Jain, Mohammad Mahdian:
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. FOCS 2004: 277-285 - Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324 - Gianni Franceschini, Roberto Grossi:
No Sorting? Better Searching! FOCS 2004: 491-498 - Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. FOCS 2004: 394-403 - Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS 2004: 562-571 - Anupam Gupta, R. Ravi, Amitabh Sinha:
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. FOCS 2004: 218-227 - Nir Halman:
On the Power of Discrete and of Lexicographic Helly-Type Theorems. FOCS 2004: 463-472 - Kamal Jain:
A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. FOCS 2004: 286-294 - Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman:
Testing Low-Degree Polynomials over Prime Fields. FOCS 2004: 423-432 - George Karakostas, Stavros G. Kolliopoulos:
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. FOCS 2004: 268-276 - Tali Kaufman, Dana Ron:
Testing Polynomials over General Fields. FOCS 2004: 413-422 - Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in Lattices. FOCS 2004: 126-135 - Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. FOCS 2004: 136-145 - Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS 2004: 146-154 - Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. FOCS 2004: 12-21 - Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler:
Triangulation and Embedding Using Small Sets of Beacons. FOCS 2004: 444-453 - Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics. FOCS 2004: 434-443 - Amit Kumar, Yogish Sabharwal, Sandeep Sen:
A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions. FOCS 2004: 454-462 - Michael Langberg:
Private Codes or Succinct Random Codes That Are (Almost) Perfect. FOCS 2004: 325-334 - Lap Chi Lau:
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. FOCS 2004: 61-70 - Jirí Matousek, Tibor Szabó:
Random Edge Can Be Exponential on Abstract Cubes. FOCS 2004: 92-100 - Daniele Micciancio, Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures. FOCS 2004: 372-381 - Carlos Mochon:
Quantum Weak Coin-Flipping with Bias of 0.192. FOCS 2004: 2-11 - Elchanan Mossel, Yuval Peres, Alistair Sinclair:
Shuffling by Semi-Random Transpositions. FOCS 2004: 572-581 - Marcin Mucha, Piotr Sankowski:
Maximum Matchings via Gaussian Elimination. FOCS 2004: 248-255 - Ran Raz:
Multilinear-NC neq Multilinear-NC. FOCS 2004: 344-351 - Liam Roditty, Uri Zwick:
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. FOCS 2004: 499-508 - Piotr Sankowski:
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). FOCS 2004: 509-517 - Rahul Savani, Bernhard von Stengel:
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. FOCS 2004: 258-267
