Difference between revisions of "Open Problems:By Number"
(Adding new problems to the list) |
m (Formatting) |
||
| Line 92: | Line 92: | ||
*{{ProblemLink|79}} | *{{ProblemLink|79}} | ||
*{{ProblemLink|80}} | *{{ProblemLink|80}} | ||
| − | |||
Problems suggested at the [[Workshops:FOCS 2017|Frontiers in Distribution Testing workshop at FOCS 2017]]: | Problems suggested at the [[Workshops:FOCS 2017|Frontiers in Distribution Testing workshop at FOCS 2017]]: | ||
Revision as of 06:29, 8 November 2017
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: Open-Shortest-Path-First 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 Graph Streams
- 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
Problems suggested at the Bertinoro Workshop on Sublinear Algorithms 2014:
- Problem 61: RNA Folding
- Problem 62: Principal Component Analysis with Nonnegativity Constraints
- Problem 63: Submodular Matching Maximization
- Problem 64: Matchings in the Turnstile Model
- Problem 65: Communication Complexity of Connectivity
- Problem 66: Distinguishing Distributions with Conditional Samples
- Problem 67: Difficult Instance for Max-Cut in the Streaming Model
- Problem 68: Approximating Rank in the Bounded-Degree Model
Problems suggested at the Sublinear Algorithms Workshop 2016 at Johns Hopkins University:
- Problem 69: Correcting Independence of Distributions
- Problem 70: Open Problems in $L_p$-Testing
- Problem 71: Metric TSP Cost Approximation
- Problem 72: Communication Complexity of Approximating Set-Intersection Join
- Problem 73: Streaming Online Algorithms
- Problem 74: Succinct Representation for Functions on Graphs
Problems suggested at the Workshop on Communication Complexity and Applications 2017 at the Banff International Research Station:
- Problem 75: Data Structure Lower Bound in the Cell Probe Model
- Problem 76: External Information and Amortized Expected Communication
- Problem 77: Frontiers in Structural Communication Complexity
- Problem 78: Linear Sketching Over $F_2$
- Problem 79: Cryptogenography
- Problem 80: Merlin–Arthur Communication Complexity of Connectivity
Problems suggested at the Frontiers in Distribution Testing workshop at FOCS 2017:
- Problem 81: Rényi Entropy Estimation
- Problem 82: Beyond Identity Testing
- Problem 83: Instance-Specific Hellinger Testing
- Problem 84: Efficient Profile Maximum Likelihood Computation
- Problem 85: Sample Stretching
- Problem 86: Equivalence Testing Lower Bound via Communication Complexity
- Problem 87: Equivalence Testing with Conditional Samples
- Problem 88: Separating PDF and CDF Query Models
- Problem 89: AM vs. NP for Proofs of Proximity in Distribution Testing
