The SCEAS System
Navigation Menu

Conferences in DBLP

Annual Symposium on Foundations of Computer Science (FOCS) (focs)
2008 (conf/focs/2008)


  1. The Polynomial Method in Quantum and Classical Computing. [Citation Graph (, )][DBLP]


  2. Theory of Sponsored Search Auctions. [Citation Graph (, )][DBLP]


  3. Average-case Complexity. [Citation Graph (, )][DBLP]


  4. Truthful Approximation Schemes for Single-Parameter Agents. [Citation Graph (, )][DBLP]


  5. Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. [Citation Graph (, )][DBLP]


  6. Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. [Citation Graph (, )][DBLP]


  7. Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. [Citation Graph (, )][DBLP]


  8. The Sign-Rank of AC^O. [Citation Graph (, )][DBLP]


  9. Arithmetic Circuits: A Chasm at Depth Four. [Citation Graph (, )][DBLP]


  10. Dense Subsets of Pseudorandom Sets. [Citation Graph (, )][DBLP]


  11. Almost-Natural Proofs. [Citation Graph (, )][DBLP]


  12. Dynamic Connectivity: Connecting to Networks and Geometry. [Citation Graph (, )][DBLP]


  13. Algorithms for Single-Source Vertex Connectivity. [Citation Graph (, )][DBLP]


  14. A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. [Citation Graph (, )][DBLP]


  15. Degree Bounded Network Design with Metric Costs. [Citation Graph (, )][DBLP]


  16. Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. [Citation Graph (, )][DBLP]


  17. Fast Modular Composition in any Characteristic. [Citation Graph (, )][DBLP]


  18. Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. [Citation Graph (, )][DBLP]


  19. Worst Case to Average Case Reductions for Polynomials. [Citation Graph (, )][DBLP]


  20. On the Union of Cylinders in Three Dimensions. [Citation Graph (, )][DBLP]


  21. Spherical Cubes and Rounding in High Dimensions. [Citation Graph (, )][DBLP]


  22. Near-Optimal Sparse Recovery in the L1 Norm. [Citation Graph (, )][DBLP]


  23. On Basing Lower-Bounds for Learning on Worst-Case Assumptions. [Citation Graph (, )][DBLP]


  24. The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). [Citation Graph (, )][DBLP]


  25. Hardness of Minimizing and Learning DNF Expressions. [Citation Graph (, )][DBLP]


  26. Elections Can be Manipulated Often. [Citation Graph (, )][DBLP]


  27. On the Hardness of Being Truthful. [Citation Graph (, )][DBLP]


  28. Multi-unit Auctions with Budget Limits. [Citation Graph (, )][DBLP]


  29. Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. [Citation Graph (, )][DBLP]


  30. On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. [Citation Graph (, )][DBLP]


  31. Leakage-Resilient Cryptography. [Citation Graph (, )][DBLP]


  32. Succincter. [Citation Graph (, )][DBLP]


  33. Two Query PCP with Sub-Constant Error. [Citation Graph (, )][DBLP]


  34. Constant-Time Approximation Algorithms via Local Improvements. [Citation Graph (, )][DBLP]


  35. Some Results on Greedy Embeddings in Metric Spaces. [Citation Graph (, )][DBLP]


  36. Set Covering with our Eyes Closed. [Citation Graph (, )][DBLP]


  37. Minimizing Movement in Mobile Facility Location Problems. [Citation Graph (, )][DBLP]


  38. A Counterexample to Strong Parallel Repetition. [Citation Graph (, )][DBLP]


  39. Rounding Parallel Repetitions of Unique Games. [Citation Graph (, )][DBLP]


  40. The Unbounded-Error Communication Complexity of Symmetric Functions. [Citation Graph (, )][DBLP]


  41. Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. [Citation Graph (, )][DBLP]


  42. Inapproximability for Metric Embeddings into R^d. [Citation Graph (, )][DBLP]


  43. A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. [Citation Graph (, )][DBLP]


  44. Hardness of Nearest Neighbor under L-infinity. [Citation Graph (, )][DBLP]


  45. (Data) STRUCTURES. [Citation Graph (, )][DBLP]


  46. Entangled Games are Hard to Approximate. [Citation Graph (, )][DBLP]


  47. Unique Games with Entangled Provers are Easy. [Citation Graph (, )][DBLP]


  48. Quantum Multi Prover Interactive Proofs with Communicating Provers. [Citation Graph (, )][DBLP]


  49. A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. [Citation Graph (, )][DBLP]


  50. Sketching and Streaming Entropy via Approximation Theory. [Citation Graph (, )][DBLP]


  51. On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. [Citation Graph (, )][DBLP]


  52. Clock Synchronization with Bounded Global and Local Skew. [Citation Graph (, )][DBLP]


  53. Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. [Citation Graph (, )][DBLP]


  54. What Can We Learn Privately? [Citation Graph (, )][DBLP]


  55. Learning Geometric Concepts via Gaussian Surface Area. [Citation Graph (, )][DBLP]


  56. Isotropic PCA and Affine-Invariant Clustering. [Citation Graph (, )][DBLP]


  57. Approximate Kernel Clustering. [Citation Graph (, )][DBLP]


  58. Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. [Citation Graph (, )][DBLP]


  59. (Acyclic) JobShops are Hard to Approximate. [Citation Graph (, )][DBLP]


  60. Linear Level Lasserre Lower Bounds for Certain k-CSPs. [Citation Graph (, )][DBLP]


  61. The Power of Reordering for Online Minimum Makespan Scheduling. [Citation Graph (, )][DBLP]


  62. Locally Testing Direct Product in the Low Error Range. [Citation Graph (, )][DBLP]


  63. Kakeya Sets, New Mergers and Old Extractors. [Citation Graph (, )][DBLP]


  64. A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. [Citation Graph (, )][DBLP]


  65. Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. [Citation Graph (, )][DBLP]


  66. Network Extractor Protocols. [Citation Graph (, )][DBLP]


  67. Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. [Citation Graph (, )][DBLP]


  68. Computing the Tutte Polynomial in Vertex-Exponential Time. [Citation Graph (, )][DBLP]


  69. On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. [Citation Graph (, )][DBLP]


  70. Submodular Approximation: Sampling-based Algorithms and Lower Bounds. [Citation Graph (, )][DBLP]


  71. Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. [Citation Graph (, )][DBLP]


  72. Noise Tolerance of Expanders and Sublinear Expander Reconstruction. [Citation Graph (, )][DBLP]


  73. Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. [Citation Graph (, )][DBLP]


  74. Size Bounds and Query Plans for Relational Joins. [Citation Graph (, )][DBLP]


  75. Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. [Citation Graph (, )][DBLP]


  76. Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. [Citation Graph (, )][DBLP]


  77. A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. [Citation Graph (, )][DBLP]


  78. Nearly Tight Low Stretch Spanning Trees. [Citation Graph (, )][DBLP]


  79. Algorithmic Barriers from Phase Transitions. [Citation Graph (, )][DBLP]


  80. Mixing Time of Exponential Random Graphs. [Citation Graph (, )][DBLP]


  81. k-Wise Independent Random Graphs. [Citation Graph (, )][DBLP]


  82. Broadcasting with Side Information. [Citation Graph (, )][DBLP]

NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002