reference-request

  1. References for the computational complexity of training neural networks

  2. 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}$?
  3. Is there any book on the philosophical implications of Theoretical Computer Science?

  4. Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
  5. Matrix Coloring under Vertical and Horizontal Constraints
  6. Most general setting for fine-grained exponential-time complexity classes?

  7. 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
  8. Stronger reductions in parameterized complexity

  9. Are there variants of visibly pushdown automata that allow pushing of words onto the stack?
  10. Is there a name for this property of a term rewriting system?

  11. Janson-type inequality, limited dependence
  12. Examples of quasilinear vs. essentially linear time translatable models

  13. Which well-known algorithmic problem is this an instance of?
  14. What is the time complexity of base conversion on a multi-tape Turing machine?

  15. Extended version of the paper "Consistent Hashing and Random Trees" with proofs
  16. What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

  17. Does the following problem have a classical name (e.g. max flow, stable matching, etc) and if so is there an efficient solution?
  18. Is there any known Poly-APX-complete minimimization problem?

  19. Program inversion algorithms for higher-order programs

  20. State of the Art for the Monadic Class?

  21. QUBO formulation of a discrete-variable optimization problem

  22. EXPSPACE-complete problems

  23. What happens when PSPACE contains NEXP?

  24. Knot Recognition as a Proof of Work System
  25. Properties of toroidal graph

  26. Bloom filter variant for constant-time subset/superset queries

  27. Is there any good and free Introduction to topological graph theory

  28. Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification
  29. Centroid in $\ell_2$ distance

  30. How to benchmark #2-SAT counting algorithms?

  31. Equality Constraints over Sets with Tree Automata
  32. Is there algorithmic mathematical analysis?
  33. Have fixed parameter integer program algorithms ever been implemented for research use?

  34. A class of functions on a lattice that are easy to optimize

  35. Deformation of finite regular languages

  36. Book Recommendations for a General Introduction to (Theoretical) Computer Science

  37. Derive a theoretical bound about coding with a partial eavesdropper
  38. Maximum Treewidth of a Graphs with $m$ Edges

  39. Chernoff bound for negatively correlated variables

  40. Complexity of Proportional Sampling

  41. Books on programming language semantics

  42. Graceful labeling completion problems

  43. What are the recent TCS books whose drafts are available online?

  44. Is Isomorphism of bounded degree hyper-graphs in P?
  45. Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?
  46. Easy instances for coset intersection problem
  47. Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

  48. Practical/heuristic algorithm for multi set-cover

  49. Correlated random models of game trees

  50. How to find largest supergroup in polynomial time?
  51. Different algorithms for longest increasing subsequence
  52. Book/ Monograph on graph minor theory [Reference request]

  53. Which Integer Linear Programs are easy?

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

  55. Math foundation for namespace problem

  56. Name for "uniformly polynomial" subclass of XP?

  57. On status of Valiant's $NC^2=P^{\#P}$ provability program?
  58. Textbook/resources for a beginning researcher in (Machine) Learning Theory

  59. Sources of open problems?

  60. Is simply typed lambda calculus equivalent to primitive recursive functions

  61. Funny TCS-related papers etc?
  62. Complexity of Homogenizing a String

  63. reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

  64. Reference for the number of samples needed to distinguish two probability distributions

  65. On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

  66. On $NP$ and $XP$ classes?

  67. Algorithm for finding heavy hitters in a weighted stream

  68. What Books Should Everyone Read?
  69. Composition of $FP$ and $\#P$ functions

  70. Counting multiplicative closures
  71. Structures obtained by gluing simplices

  72. research papers for undergraduate students

  73. Status of constant-depth isomorphism in $AC^0[\oplus]$

  74. Notion of "total work" of a problem?

  75. Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

  76. Graph addition chains

  77. Inference in typed lambda calculus theories

  78. Is intersection of $k \ge 3$ graphic matroids in P?

  79. Can one amplify P=NP beyond P=PH?
  80. Is there a relationship between relational algebra/calculus and category theory?

  81. Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

  82. Log space algorithms for modular decomposition tree
  83. A sequence wherein the Kolmogorov complexity of the terms does not increase

  84. "Almost sorting" integers in linear time

  85. Vertex isoperimetric number of a graph - NP-hard?

  86. Deterministic approximation algorithms for treewidth

  87. Is the 3-sphere recognition problem NP-complete?
  88. How to extend Solomonoff Induction to continuous domain
  89. Was counting complexity first introduced by Valiant in 1979?
  90. Hard extendability problems
  91. Deterministic Parallel algorithm for perfect matching in general graphs?

  92. Using epsilon biased sets for circuit lower bounds

  93. Efficient training algorithm for a generalized version of SVM
  94. Complexity of checking if two words have an interleaving in a language

  95. Approximate degree of $\textrm{AC}^0$

  96. Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

  97. Fastest known deterministic algorithm for the undirected Graph Isomorphism problem
  98. Word length using entropy : Maximum entropy criteria
  99. Efficiently ordering typed programs

  100. SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms