Difference between revisions of "Open Problems:By Number"
| Line 1: | Line 1: | ||
Problems suggested at the [[Workshops:Kanpur_2006|IITK Workshop on Algorithms for Data Streams 2006]]: | Problems suggested at the [[Workshops:Kanpur_2006|IITK Workshop on Algorithms for Data Streams 2006]]: | ||
| − | * | + | *{{ProblemLink|1}} |
| − | * | + | *{{ProblemLink|2}} |
| − | * | + | *{{ProblemLink|3}} |
| − | * | + | *{{ProblemLink|4}} |
| − | * | + | *{{ProblemLink|5}} |
| − | * | + | *{{ProblemLink|6}} |
| − | * | + | *{{ProblemLink|7}} |
| − | * | + | *{{ProblemLink|8}} |
| − | * | + | *{{ProblemLink|9}} |
| − | * | + | *{{ProblemLink|10}} |
| − | * | + | *{{ProblemLink|11}} |
| − | * | + | *{{ProblemLink|12}} |
| − | * | + | *{{ProblemLink|13}} |
| − | * | + | *{{ProblemLink|14}} |
| − | * | + | *{{ProblemLink|15}} |
| − | * | + | *{{ProblemLink|16}} |
| − | * | + | *{{ProblemLink|17}} |
| − | * | + | *{{ProblemLink|18}} |
| − | * | + | *{{ProblemLink|19}} |
| − | * | + | *{{ProblemLink|20}} |
| − | * | + | *{{ProblemLink|21}} |
Problems suggested at the [[Workshops:Kanpur_2009|IITK Workshop on Algorithms for Processing Massive Data Sets 2009]]: | Problems suggested at the [[Workshops:Kanpur_2009|IITK Workshop on Algorithms for Processing Massive Data Sets 2009]]: | ||
| − | * | + | *{{ProblemLink|22}} |
| − | * | + | *{{ProblemLink|23}} |
| − | * | + | *{{ProblemLink|24}} |
| − | * | + | *{{ProblemLink|25}} |
| − | * | + | *{{ProblemLink|26}} |
| − | * | + | *{{ProblemLink|27}} |
| − | * | + | *{{ProblemLink|28}} |
| − | * | + | *{{ProblemLink|29}} |
| − | * | + | *{{ProblemLink|30}} |
| − | * | + | *{{ProblemLink|31}} |
| − | * | + | *{{ProblemLink|32}} |
| − | * | + | *{{ProblemLink|33}} |
| − | * | + | *{{ProblemLink|34}} |
| − | * | + | *{{ProblemLink|35}} |
Problems suggested at the [[Workshops:Bertinoro_2011|Bertinoro Workshop on Sublinear Algorithms 2011]]: | Problems suggested at the [[Workshops:Bertinoro_2011|Bertinoro Workshop on Sublinear Algorithms 2011]]: | ||
| − | * | + | *{{ProblemLink|36}} |
| − | * | + | *{{ProblemLink|37}} |
| − | * | + | *{{ProblemLink|38}} |
| − | * | + | *{{ProblemLink|39}} |
| − | * | + | *{{ProblemLink|40}} |
| − | * | + | *{{ProblemLink|41}} |
| − | * | + | *{{ProblemLink|42}} |
| − | * | + | *{{ProblemLink|43}} |
| − | * | + | *{{ProblemLink|44}} |
| − | * | + | *{{ProblemLink|45}} |
| − | * | + | *{{ProblemLink|46}} |
| − | * | + | *{{ProblemLink|47}} |
| − | * | + | *{{ProblemLink|48}} |
| − | * | + | *{{ProblemLink|49}} |
| − | * | + | *{{ProblemLink|50}} |
Problems suggested at the [[Workshops:Dortmund_2012|Dortmund Workshop on Algorithms for Data Streams 2012]]: | Problems suggested at the [[Workshops:Dortmund_2012|Dortmund Workshop on Algorithms for Data Streams 2012]]: | ||
| − | * | + | *{{ProblemLink|51}} |
| − | * | + | *{{ProblemLink|52}} |
| − | * | + | *{{ProblemLink|53}} |
| − | * | + | *{{ProblemLink|54}} |
| − | * | + | *{{ProblemLink|55}} |
| − | * | + | *{{ProblemLink|56}} |
| − | * | + | *{{ProblemLink|57}} |
| − | * | + | *{{ProblemLink|58}} |
| − | * | + | *{{ProblemLink|59}} |
| − | * | + | *{{ProblemLink|60}} |
Revision as of 01:30, 7 March 2013
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
