co.combinatorics

  1. NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
  2. Continous work distribution algorithm with failover
  3. How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

  4. Proving that a random permutation generator is not fair
  5. Is there any good and free Introduction to topological graph theory

  6. Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

  7. Finding the longest sub-permutation with bounded inversion number
  8. Wavelet based Non linear optimization technique
  9. Is Hartmanis-Stearns conjecture settled by this article?

  10. A dynamic packing problem

  11. Derive a theoretical bound about coding with a partial eavesdropper

  12. Application of graph theory in computer science
  13. Using error-correcting codes in theory

  14. Sum of products of all combinations with replacement
  15. Finding subgraphs with high treewidth and constant degree
  16. Does the first order theory of a finite structure have bounded quantifier rank?

  17. Reference: Cancellability of the Dyck congruence

  18. Relation between variance and mutual information

  19. Directed graph with bounded in-deg can be partitioned in a balanced way

  20. Stochastic dynamic programming problem that is Approximation-hard

  21. Short supersequence for many permutations

  22. Almost regular subhypergraph of hypergraph with large minimal degree

  23. Existence of $d$-regular expander graph that can be represented as a bipartite graph
  24. How to construct an $(n,m,k)$ ``separating set''?

  25. Just how bad is the fooling set method in communication complexity?

  26. Counting xyz-graphs in $\mathbb{Z}_n^3$

  27. Is optimally solving the n×n×n Rubik's Cube NP-hard?

  28. Counting multiplicative closures
  29. Reference request: exponential growth rates of subsequence-closed languages are integers
  30. Graph addition chains

  31. Pathwidth of planarized drawing of $K_{3,n}$
  32. Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

  33. Increasing the capacity to maximize the min cut
  34. Scheduling to maximize idle time

  35. How to prove "obvious" facts?

  36. Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

  37. An edge partitioning problem on cubic graphs

  38. VC dimension of polynomials over tropical semirings?
  39. Families of LDPC codes with constant error fraction corrected
  40. Category theory, computational complexity, and combinatorics connections?

  41. Counting subsets of given set with certain properties
  42. Computing the Fourier expansion of the complete quadratic function

  43. Implementation of Wilf-Zeilberger and related methods

  44. If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

  45. Pairwise comparison of bit vectors

  46. Constructing a large bit-vector set with the following property

  47. Is any chordal graph an incomparability graph?

  48. Counting the Number of Simple Paths in Undirected Graph

  49. Was this complexity measure studied before?
  50. Counting words accepted by a regular grammar
  51. A property of suffix-free regular languages of maximal state complexity for the reverse operation
  52. Random walk and mean hitting time in a simple undirected graph

  53. expected number of edges for fixed min cut

  54. reference request- property of subset of rows in a matrix

  55. What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

  56. $NP$-completeness of recognizing the difference of two permutations

  57. Enumerating all simply typed lambda terms of a given type
  58. Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?

  59. Number of local maxima in MAX-2-SAT

  60. Computing Minima of the Projection of a Binary Cube

  61. Degree distribution of certain subgraphs of a biregular graph

  62. Can the "mutual independence" condition in the Lovász local lemma be weakened?
  63. Structured set of binary words
  64. The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

  65. Can you identify the sum of two permutations in polynomial time?
  66. 3-color a cubic graph such that a MIS receives only two colors
  67. The maximum number of induced cycles in a simple directed graph

  68. Edge-partitioning cubic graphs into claws and paths

  69. Voronoi Diagram of Lines
  70. Is there any efficient algorithm for computing all semigroups of order n?

  71. How many tautologies are there?
  72. Fast Approximation Algorithms for Covering Design

  73. Number of mincuts of a graph without using Karger's algorithm
  74. Is this graph polynomial known? Can it be efficiently computed?
  75. Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

  76. Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges
  77. Matching of points in two discrete linear sequences with potentially missing points
  78. The relationship between degree of vertex and size of dominating set
  79. Computational Complexity of Ramsey Numbers
  80. Subset of a bipartite graph with maximal number of minimal unmatched vertices

  81. Optimal distribution of integer edge weights
  82. Generate connected induced subgraphs as the satisfying assignments to a SAT instance
  83. Maintain mex with efficient union
  84. Distance between Sum Sets and Another Point
  85. Has this form of "kind-of-dual" homomorphisms been studied?

  86. Embedding distortion under group quotient
  87. Grid minor in digraphs

  88. The complexity of decomposing a bi-stochastic matrix

  89. Partitions on Integer Permutations

  90. Reconstructing word / permutation

  91. Maximize number of bins and minimize cost of elements chosen from a set
  92. Math talk: Theorem about git revision control system?

  93. How hard is recognizing a permutation that is a square for the shift product?
  94. Approximations for the Stable Fixtures Problem

  95. Is it decidable to determine if a given shape can tile the plane?

  96. A simple challenge
  97. Construction of a graph which has regular subgraphs at each iteration of a recursive process

  98. Constant in Komlos conjecture

  99. Permutations with forbidden subsequences

  100. How many distinct colors are needed to lower-bound the choosability of a graph?