Open Problems:By Number
Revision as of 20:18, 1 October 2012 by Krzysztof Onak (talk | contribs)
Problems suggested at the IITK Workshop on Algorithms for Data Streams 2006:
- Problem 1: Fast $L_1$ Difference
- Problem 2: Quantiles
- Problem 3: $L_\infty$ Estimation
- Problem 4: Deterministic Summary Structures
- Problem 5: Characterizing Sketchable Distances
- Problem 6: Filtering Irrelevant Data
- Problem 7: Estimating Earth-Mover Distance
- Problem 8: Mixed Norms
- Problem 9: OSPF Routing
- Problem 10: Multi-Round Communication of Gap-Hamming Distance
- Problem 11: Counting Triangles
- Problem 12: Deterministic $CUR$-Type Decompositions
- Problem 13: Effects of Subsampling
- Problem 14: Graph Distances
- Problem 15: Semi-Random Streams
- Problem 16: Graph Matchings
- Problem 17: The Massive, Unordered, Distributed-Data Model
- Problem 18: Finite Cursor Machines
- Problem 19: Sketching vs. Streaming
- Problem 20: Relations between Streaming Models
- Problem 21: Deterministic Heavy-Hitters & Fast Matrix Algorithms
Problems suggested at the IITK Workshop on Algorithms for Processing Massive Data Sets 2009:
- Problem 22: Random Walks
- Problem 23: Approximate 2D Width
- Problem 24: “Ultimate” Deterministic Sparse Recovery
- Problem 25: Communication Complexity and Metric Spaces
- Problem 26: Equivalence of Two MapReduce Models
- Problem 27: Modeling of Distributed Computation
- Problem 28: Randomness of Partially Random Streams
- Problem 29: Strong Lower Bounds for Graph Problems
- Problem 30: Universal Sketching
- Problem 31: Gap-Hamming Information Cost
- Problem 32: The Value of a Reverse Pass
- Problem 33: Group Testing
- Problem 34: Linear Algebra Computation
- Problem 35: Maximal Complex Equiangular Tight Frames
Problems suggested at the Bertinoro Workshop on Sublinear Algorithms 2011:
- Problem 36: Learning an $f$-Transformed Product Distribution
- Problem 37: Testing Submodularity
- Problem 38: Query Complexity of Local Partitioning Oracles
- Problem 39: Approximating Maximum Matching Size
- Problem 40: Testing Monotonicity and the Lipschitz Property
- Problem 41: Testing Acyclicity
- Problem 42: Graph Frequency Vectors
- Problem 43: Rank Lower Bound
- Problem 44: Approximating LIS Length in the Streaming Model
- Problem 45: Streaming Max-Cut/Max-CSP
- Problem 46: Fast JL Transform for Sparse Vectors
- Problem 47: Annotated Streaming
- Problem 48: Sketching Shift Metrics
- Problem 49: Sketching Earth Mover Distance
- Problem 50: Sparse Recovery for Tree Models
Problems suggested at the Dortmund Workshop on Algorithms for Data Streams 2012:
- Problem 51: “For All” Guarantee for Computationally Bounded Adversaries
- Problem 52: TSP in the Streaming Model
- Problem 53: Homomorphic Hash Functions
- Problem 54: Faster JL Dimensionality Reduction
- Problem 55: Applications of Clifford Algebras in Streaming
- Problem 56: Efficient Measures of “Surprisingness” of Sequences
- Problem 57: Coding Theory in the Streaming Model
- Problem 58: Signatures for Set Equality
- Problem 59: Low Expansion Encoding of Edit Distance
- Problem 60: Single-Pass Unweighted Matchings
