cc.complexity-theory

  1. Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
  2. Is Normal centralizer problem in P?

  3. On $NP$, $\oplus P$ and $PP$?

  4. NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
  5. Beating naive dynamic programming: examples similar to integer partitions?
  6. Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al
  7. Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

  8. How fine-grained can the time hierarchy theorem be in a reasonable model?
  9. Functions that are Not Efficiently Computable but Learnable

  10. Can neural networks be used to devise algorithms?
  11. Buckets in Hopcroft-Ullman analysis of Union-Find
  12. Complexity of a variant of partition problem

  13. Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

  14. Is there a P-complete problem on diophantine equations?

  15. Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

  16. Chaos and the $P{=}NP$ question

  17. Randomized Algorithm Analysis
  18. Convention for RAM machine models

  19. Reduction of graph chromatic number to hypergraph 2-colorability

  20. Fine-grained complexity of BPP
  21. Stronger reductions in parameterized complexity
  22. Is BPP= P known for ANY uniform model of computation?
  23. Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

  24. Direct SAT to 3-SAT reduction
  25. Proof assistant usage in complexity theory research?

  26. Formally Verified Complexity Theory

  27. Strongly NP-complete variants of subset sum or partition problem

  28. Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

  29. Two queries related to Toda
  30. What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$
  31. Binary rank of binary matrix

  32. Does there exist an ontology for algorithms?

  33. Successful examples where relativization barrier has been circumvented?
  34. Complexity class on quantum computation and classic ones

  35. On collapsing the Exponential time hierarchy

  36. Proof: PTIME not equal EXPTIME
  37. EXPSPACE-complete problems
  38. What happens when PSPACE contains NEXP?
  39. What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?

  40. Knot Recognition as a Proof of Work System

  41. What is the time complexity of increasing the precision of finding matrix eigenvalues?
  42. To what extent, computational ability for hard tasks helps in solving easy tasks

  43. On approximating problems in $\#P$

  44. Conclusions from reverse mathematical strength of graph minor theorem
  45. Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
  46. #P-complete problem whose decision version is in P
  47. Number of minimal DFAs of size at most $m$?
  48. Lowest common ancestor on selected nodes in a tree

  49. Complexity of n-queens-completion?
  50. What are some known methods for showing that a class has no complete problems?
  51. When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

  52. Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
  53. Complexity of the mandelbrot set on rationals

  54. Quantum polynomial hierarchy vs counting hierarchy
  55. Does $NP=PP$ collapse the counting hierarchy?

  56. Is BPP vs. P a real problem after we know BPP lies in P/poly?
  57. Wavelet based Non linear optimization technique

  58. Some questions about the depth hierarchy for threshold circuits
  59. Is Hartmanis-Stearns conjecture settled by this article?

  60. What's the "smallest" complexity class for which a superlinear circuit bound is known?

  61. Is there algorithmic mathematical analysis?

  62. How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

  63. Reference for a circuit lower bound for slightly superexponential time

  64. Is scalable hardware support for LogCFL (= sAC^1) possible?

  65. Hardness of exact binomial tail bounds

  66. What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?
  67. Time Hierarchies in DSPACE(O(s(n)))
  68. Is sliding blocks linear space complete?

  69. Finding a sub rectangle with maximum sum
  70. Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

  71. Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
  72. Are runtime bounds in P decidable? (answer: no)

  73. Is TSP in the plane with rational coordinates NP-complete?

  74. What is the largest distance that still guarantees a linear time distance search?

  75. Example of something that’s different for generic and random oracles?

  76. In what class are randomized algorithms that err with exactly 25% chance?
  77. Can $f^{2^N}(x)$ be computed in polynomial time when $f$ is linear?

  78. Justification of log f in DTIME hierarchy theorem
  79. Complexity Class Equalities on the Edge of Inconsistency

  80. Deciding the Most Significant Bit of Binary Multiplication
  81. Graceful labeling completion problems
  82. Is the N Queens problem NP-hard?
  83. Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
  84. Is Asymptotic PTAS $\subseteq$ APX?

  85. Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$
  86. String version of even-odd partition problem

  87. Wikipedia-style explanation of Geometric Complexity Theory
  88. Power of randomness vs. power of indefinite computation

  89. Are there NP-complete problems with polynomial expected time solutions?
  90. Logarithmic levels of the polynomial hierarchy (below PSPACE)
  91. Is there known any complexity class containing online counterparts of optimization problems?

  92. Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

  93. Example demonstrating the power of non-deterministic circuits

  94. Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

  95. Tardos Function Counterexample to Blum's $P\neq NP$ Claim

  96. Razborov's Approximation methods
  97. High-level overview of Razborov's method of approximations

  98. Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

  99. Average case or beyond worse case analysis for non-convex optimization procedures?

  100. What exactly did Lenstra prove on mixed integer linear program?