Difference between revisions of "Open Problems:By Number"
(Adding the problems from the workshop in Warwick in 208) |
(Adding WOLA problems) |
||
| Line 110: | Line 110: | ||
*{{ProblemLink|93}} | *{{ProblemLink|93}} | ||
*{{ProblemLink|94}} | *{{ProblemLink|94}} | ||
| + | |||
| + | Problems suggested at the [[Workshops:WOLA_2019|Workshop on Local Algorithms 2019 at ETH Zurich]]: | ||
| + | *{{ProblemLink|95}} | ||
| + | *{{ProblemLink|96}} | ||
| + | *{{ProblemLink|97}} | ||
| + | *{{ProblemLink|98}} | ||
| + | *{{ProblemLink|99}} | ||
| + | *{{ProblemLink|100}} | ||
| + | *{{ProblemLink|101}} | ||
| + | *{{ProblemLink|102}} | ||
Latest revision as of 18:09, 26 August 2019
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
Problems suggested at the Workshop on Data Summarization at the University of Warwick in 2018:
- Problem 90: Dense Graph Property Testing “Tradeoffs”
- Problem 91: Cut-Sparsification of Hypergraphs
- Problem 92: Streaming Algorithms for Approximating the Number of $H$-Subgraphs
- Problem 93: Locally Private Heavy Hitters and Other Problems in Streaming
- Problem 94: Ads, Impressions, and Statistics
Problems suggested at the Workshop on Local Algorithms 2019 at ETH Zurich:
- Problem 95: Non-Adaptive Group Testing
- Problem 96: Identity Testing up to Coarsenings
- Problem 97: Local Computation Algorithm for MIS
- Problem 98: Estimating a Graph's Degree Distribution
- Problem 99: Vertex-Distribution-Free Graph Testing
- Problem 100: Effective Support Size Estimation in the Dual Model
- Problem 101: Vertex Connectivity in the LOCAL Model
- Problem 102: Making Edges Happy in the LOCAL Model
