List of subject areas

1. Complexity

  1. Uniform Complexity (Turing machine-based complexity classes, excluding Randomized Complexity and Relativized Complexity)
  2. Relativized Complexity
  3. Randomized Complexity Classes (BPP, AM, Interactive proofs excluding Zero Knowledge)
  4. Algebraic Complexity
  5. Nonuniform Complexity (communication complexity, circuit complexity, branching programs, decision trees, formula size, sensitivity, etc.) excluding Proof Complexity
  6. Proof Complexity
  7. Logic, Descriptive Complexity, Formal Languages, Rewriting
  8. Random Structures (properties of random objects, percolation, phase transition)
  9. Pseudorandomness (derandomization, extractors, expanders, "hardness vs randomness")
  10. Computational Coding Theory
  11. Inapproximability, PCPs
  12. Property Testing
  13. Zero Knowledge
  14. Cryptography other than Zero Knowledge
  15. Lower Bounds but none of the above
  16. Complexity but none of the above

2. Classical Algorithmic Models

  1. Fundamental Algorithms (sorting, searching, string matching, etc.)
  2. Scheduling, Load Balancing, Bin Packing
  3. Graph Algorithms: network flows, cuts, bisection, connectivity
  4. Graph Algorithms: shortest paths, min spanning tree, Steiner trees, facility location
  5. Graph Algorithms but none of the above (including matchings, coloring, cliques, crossing number, etc.)
  6. Network Design
  7. Data Structures, Dynamic Algorithms, Hierarchical Memory Models
  8. Random processes (Markov chains, rapid mixing, generation of random objects)
  9. Combinatorial Optimization (exclduding graph algorithms)
  10. Linear and Convex Programming, Semidefinite Programming
  11. Lattice Algorithms
  12. Approximation Algorithms
  13. Metric Spaces, Embeddings
  14. Discrete Geometry
  15. Computational Geometry
  16. Classical Algorithmic Models except the mathematical algorithms listed below but none of the above

3. Mathematical Algorithms

  1. Computational Group Theory
  2. Computational Commutative Algebra, Grobner Bases
  3. Computational Number Theory
  4. Matrix Multiplication and related questions
  5. Computational Topology
  6. Numerical Computation
  7. Mathematical Algorithms but none of the above

4. Alternative Models

  1. Distributed algorithms and protocols, Byzantine agreement
  2. Online algorithms, competitive analysis
  3. Quantum Computing
  4. Learning Theory
  5. Game theory (Nash equilibrium, etc.)
  6. Data mining, clustering, recommendation systems
  7. Stream model
  8. Network algorithms, routing, gossiping
  9. Computational Biology
  10. Alternative models but none of the above.

5. Belongs to STOC but none of the above.

6. Mathematical Competence Required

  1. Number Theory
  2. Group Theory
  3. Commutative Algebra, Algebraic Geometry
  4. Galois Theory, Algebraic Geometry over Finite Fields, Algebraic Coding Theory
  5. Algebraic Topology
  6. Logic, Model theory
  7. Fourier Analysis (discrete and continuous)
  8. Mathematical Analysis (other than Fourier Analysis)
  9. Stochastic processes
  10. Advanced Mathematics other than Discrete Mathematics but none of the above

Return to the Call for Papers.

Return to the Submission Instructions.

Back to STOC'04 HOME.