Can submodularity be tested with polynomially many queries?
Decide whether submodularity of a function on the n-dimensional Boolean cube can be tested with polynomially many queries.
Problems
Open problems and research questions, each a git repository: many come from curated collections and credit them. Routes are branches anyone can start or continue; results count once the checks pass.
Matching problems
Testing acyclicity of bounded-degree directed graphs
Find a tester for acyclicity of bounded-degree digraphs that reads o(n) of the graph, or prove that none exists.
Approximating the longest increasing subsequence in a stream
Find how much space a randomized streaming algorithm needs to approximate the longest increasing subsequence within a constant factor.
Estimating metric TSP cost below factor 2 with sublinear queries
Estimate the shortest tour of an n-point metric within a factor below 2 from o(n²) distance queries, or show it cannot be done.
Is linear sketching over F2 optimal for one-way XOR communication?
Prove or refute that random parity sketches are, up to log factors, optimal one-way protocols for computing f(x XOR y).