Theoretical Computer Science

theoretical computer scientists and researchers in related fields
Solved Questions
Unsolved Questions
  1. Polynomial hierarchy in communication complexity?
  2. NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
  3. In the Hott book, are the most of the type formers redundant? And if so, why?

  4. SAMECONFIG language is PSPACE-complete

  5. Beating naive dynamic programming: examples similar to integer partitions?

  6. How to be more "theory-minded"?
  7. When it is said an algorithm runs in exponential time, is it meant it has complexity O(2^n), or 2^O(n)?
  8. Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

  9. Enumerating decidable languages
  10. Regular language that discriminates between two deterministic CFGs
  11. Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

  12. Proving properties about a compilation from one problem into another
  13. Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

  14. Use of physical environment to obtain useful results
  15. Möbius values of CNF and DNF lattices of a monotone Boolean function

  16. Is there any version of a Turing machine that can generate points of a specified probability distribution?

  17. Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

  18. Set of total functions is countable for non-equivalent turing machines

  19. How fine-grained can the time hierarchy theorem be in a reasonable model?

  20. Is there any book on the philosophical implications of Theoretical Computer Science?
  21. Lower bound on the complexity of projection onto simplex?
  22. Are there wholistic models of the universe in terms of Quantum Complexity?

  23. exact cover problem with Simulated annealing or genitics algorithms
  24. Functions that are Not Efficiently Computable but Learnable

  25. Can neural networks be used to devise algorithms?

  26. Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

  27. What would be implied regarding P and NP if a P-complete was shown to be not NP-complete?

  28. Non-Uniform Classes of Languages not Closed Under Complement

  29. What do stronger circuit lower bounds give in terms of derandomization?
  30. Is Biological Computation a theme covered by the Theoretical Computer Science?

  31. size of the induced matching

  32. Space efficient "industrial" unbalanced expanders

  33. Yao's Minimax Principle on Monte Carlo Algorithms

  34. Buckets in Hopcroft-Ullman analysis of Union-Find

  35. Confusion about "moves" in the valency argument for consensus numbers
  36. Complexity of a variant of partition problem

  37. Continous work distribution algorithm with failover

  38. Does crossover take the parents or the offsprings? How to select parents with linear ranking?
  39. Difference between weak duality and strong duality?
  40. Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

  41. Quantum computing
  42. Maximum weight non-overlapping paths in a DAG
  43. Minimum cut on a directed graph with negative term
  44. Is there a P-complete problem on diophantine equations?
  45. The Maxwell's Demon and Computer Science

  46. Knapsack with dependent profits (pairs of items)

  47. Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
  48. Chaos and the $P{=}NP$ question
  49. Approximating max coverage problem with slightly more than K sets
  50. Distributing a binary relation into bins such that each element is in a small number of bins
  51. Understanding the No Free Lunch Theorem
  52. Suggested approach to cover data structure literature
  53. Frequency-Count List Accessing Algo - Why free transpositions?

  54. Program equivalence wherein the programs are known to always halt

  55. How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
  56. Could computers calculate time before it happens in the future?

  57. Automated proving that a program doesn't halt
  58. Minimal Cost of Eulerian Path

  59. What is "Effects" in Program Graph?

  60. Randomized Algorithm Analysis

  61. Matrix Coloring under Vertical and Horizontal Constraints

  62. Convention for RAM machine models

  63. Most general setting for fine-grained exponential-time complexity classes?
  64. problem extracting correct results using relational algebra

  65. Reduction of graph chromatic number to hypergraph 2-colorability
  66. Basic property of boolean functions with restrictions
  67. Fine-grained complexity of BPP
  68. Extended Church-Turing Thesis
  69. Where is relational parametricity in hyperdoctrine or topos models explored?

  70. Graph sparsification and eigenspaces
  71. Is there a notion of computability on sets other than the natural numbers?

  72. The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously

  73. Why do spectral ultrasparsifiers need to be trees

  74. Computational Tree Logic (CTL) Proof

  75. Stronger reductions in parameterized complexity
  76. Counting the number of connected components in a dynamic plane graph

  77. An alternative formulation of max flow problem

  78. Edges that don't support non zero flow in any maximum flow

  79. Stacks serving interval storage requests

  80. Is this generalization of context free grammars known and strict?

  81. Learning a discrete distribution in $\ell_r$ norm

  82. Need explanation about asynchronous IO automaton
  83. Simulate a process of state change with transition probability dependent on proportion in state in previous time
  84. Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

  85. Finding a common factor in $\lambda$-terms that agree under certain substitutions

  86. Minimizing a sum of thresholded quadratics
  87. "Context" understanding in tree grammars

  88. Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

  89. references for optimal computation under memory constraint?

  90. Why isn't the Charikar algorithm for finding the densest subgraph optimal?
  91. Is BPP= P known for ANY uniform model of computation?
  92. Is there a name for this property of a term rewriting system?

  93. Efficient Online Algorithms for Matrix rank

  94. Sufficient conditions for the collapse of Polynomial Hierarchy (PH)
  95. Unbalanced connected partition
  96. Direct SAT to 3-SAT reduction

  97. On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits

  98. Janson-type inequality, limited dependence
  99. A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?

  100. Examples of quasilinear vs. essentially linear time translatable models