| 2000 | More general completeness theorems for secure two-party computation. | Joe Kilian |
| 2000 | Polynomial-time approximation scheme for data broadcast. | Claire Kenyon, Nicolas Schabanel, Neal E. Young |
| 2000 | Connectivity and inference problems for temporal networks. | David Kempe, Jon M. Kleinberg, Amit Kumar |
| 2000 | Complete characterization of security notions for probabilistic private-key encryption. | Jonathan Katz, Moti Yung |
| 2000 | On the efficiency of local decoding procedures for error-correcting codes. | Jonathan Katz, Luca Trevisan |
| 2000 | The risk profile problem for stock portfolio optimization (extended abstract). | Ming-Yang Kao, Andreas Nolte, Stephen R. Tate |
| 2000 | Circuit minimization problem. | Valentine Kabanets, Jin-yi Cai |
| 2000 | A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. | Satoru Iwata, Lisa Fleischer, Satoru Fujishige |
| 2000 | Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract). | Sorin Istrail |
| 2000 | Extractors and pseudo-random generators with optimal seed length. | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 2000 | Higher lower bounds on monotone size. | Danny Harnik, Ran Raz |
| 2000 | Normal subgroup reconstruction and quantum computation using group representations. | Sean Hallgren, Alexander Russell, Amnon Ta-Shma |
| 2000 | Satisfiability of equations in free groups is in PSPACE. | Claudio Gutierrez |
| 2000 | A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. | Leonid Gurvits, Alex Samorodnitsky |
| 2000 | List decoding algorithms for certain concatenated codes. | Venkatesan Guruswami, Madhu Sudan |
| 2000 | A constant factor approximation algorithm for a class of classification problems. | Anupam Gupta, va Tardos |
| 2000 | Rapid sampling though quantum computing. | Lov K. Grover |
| 2000 | Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). | Roberto Grossi, Jeffrey Scott Vitter |
| 2000 | Isomorphism testing for embeddable graphs through definability. | Martin Grohe |
| 2000 | More theory revision with queries (extended abstract). | Judy Goldsmith, Robert H. Sloan |
| 2000 | Combining fairness with throughput: online routing with multiple objectives. | Ashish Goel, Adam Meyerson, Serge A. Plotkin |
| 2000 | Approximating permanents of complex matrices. | Martin Frer |
| 2000 | Exact computations of the inertia symmetric integer matrices. | Steven Fortune |
| 2000 | Improved algorithms for submodular function minimization and submodular flow. | Lisa Fleischer, Satoru Iwata |
| 2000 | From partial consistency to global broadcast. | Matthias Fitzi, Ueli M. Maurer |