Difference between revisions of "Open Problems:By Number"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Formatting)
(12 intermediate revisions by 3 users not shown)
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]]:
*[[Open_Problems:1|Problem 1: Fast $L_1$ Difference]]
+
*{{ProblemLink|1}}
*[[Open_Problems:2|Problem 2: Quantiles]]
+
*{{ProblemLink|2}}
*[[Open_Problems:3|Problem 3: $L_\infty$ Estimation]]
+
*{{ProblemLink|3}}
*[[Open_Problems:4|Problem 4: Deterministic Summary Structures]]
+
*{{ProblemLink|4}}
*[[Open_Problems:5|Problem 5: Characterizing Sketchable Distances]]
+
*{{ProblemLink|5}}
*[[Open_Problems:6|Problem 6: Filtering Irrelevant Data]]
+
*{{ProblemLink|6}}
*[[Open_Problems:7|Problem 7: Estimating Earth-Mover Distance]]
+
*{{ProblemLink|7}}
*[[Open_Problems:8|Problem 8: Mixed Norms]]
+
*{{ProblemLink|8}}
*[[Open_Problems:9|Problem 9: Open-Shortest-Path-First Routing Routing]]
+
*{{ProblemLink|9}}
*[[Open_Problems:10|Problem 10: Multi-Round Communication of Gap-Hamming Distance]]
+
*{{ProblemLink|10}}
*[[Open_Problems:11|Problem 11: Counting Triangles]]
+
*{{ProblemLink|11}}
*[[Open_Problems:12|Problem 12: Deterministic $CUR$-Type Decompositions]]
+
*{{ProblemLink|12}}
*[[Open_Problems:13|Problem 13: Effects of Subsampling]]
+
*{{ProblemLink|13}}
*[[Open_Problems:14|Problem 14: Graph Distances]]
+
*{{ProblemLink|14}}
*[[Open_Problems:15|Problem 15: Semi-Random Streams]]
+
*{{ProblemLink|15}}
*[[Open_Problems:16|Problem 16: Graph Matchings]]
+
*{{ProblemLink|16}}
*[[Open_Problems:17|Problem 17: The Massive, Unordered, Distributed-Data Model]]
+
*{{ProblemLink|17}}
*[[Open_Problems:18|Problem 18: Finite Cursor Machines]]
+
*{{ProblemLink|18}}
*[[Open_Problems:19|Problem 19: Sketching vs. Streaming]]
+
*{{ProblemLink|19}}
*[[Open_Problems:20|Problem 20: Relations between Streaming Models]]
+
*{{ProblemLink|20}}
*[[Open_Problems:21|Problem 21: Deterministic Heavy-Hitters & Fast Matrix Algorithms]]
+
*{{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]]:
*[[Open_Problems:22|Problem 22: Random Walks]]
+
*{{ProblemLink|22}}
*[[Open_Problems:23|Problem 23: Approximate 2D Width]]
+
*{{ProblemLink|23}}
*[[Open_Problems:24|Problem 24: “Ultimate” Deterministic Sparse Recovery]]
+
*{{ProblemLink|24}}
*[[Open_Problems:25|Problem 25: Communication Complexity and Metric Spaces]]
+
*{{ProblemLink|25}}
*[[Open_Problems:26|Problem 26: Equivalence of Two MapReduce Models]]
+
*{{ProblemLink|26}}
*[[Open_Problems:27|Problem 27: Modeling of Distributed Computation]]
+
*{{ProblemLink|27}}
*[[Open_Problems:28|Problem 28: Randomness of Partially Random Streams]]
+
*{{ProblemLink|28}}
*[[Open_Problems:29|Problem 29: Strong Lower Bounds for Graph Problems]]
+
*{{ProblemLink|29}}
*[[Open_Problems:30|Problem 30: Universal Sketching]]
+
*{{ProblemLink|30}}
*[[Open_Problems:31|Problem 31: Gap-Hamming Information Cost]]
+
*{{ProblemLink|31}}
*[[Open_Problems:32|Problem 32: The Value of a Reverse Pass]]
+
*{{ProblemLink|32}}
*[[Open_Problems:33|Problem 33: Group Testing]]
+
*{{ProblemLink|33}}
*[[Open_Problems:34|Problem 34: Linear Algebra Computation]]
+
*{{ProblemLink|34}}
*[[Open_Problems:35|Problem 35: Maximal Complex Equiangular Tight Frames]]
+
*{{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]]:
*[[Open_Problems:36|Problem 36: Learning an $f$-Transformed Product Distribution]]
+
*{{ProblemLink|36}}
*[[Open_Problems:37|Problem 37: Testing Submodularity]]
+
*{{ProblemLink|37}}
*[[Open_Problems:38|Problem 38: Query Complexity of Local Partitioning Oracles]]
+
*{{ProblemLink|38}}
*[[Open_Problems:39|Problem 39: Approximating Maximum Matching Size]]
+
*{{ProblemLink|39}}
*[[Open_Problems:40|Problem 40: Testing Monotonicity and the Lipschitz Property]]
+
*{{ProblemLink|40}}
*[[Open_Problems:41|Problem 41: Testing Acyclicity]]
+
*{{ProblemLink|41}}
*[[Open_Problems:42|Problem 42: Graph Frequency Vectors]]
+
*{{ProblemLink|42}}
*[[Open_Problems:43|Problem 43: Rank Lower Bound]]
+
*{{ProblemLink|43}}
*[[Open_Problems:44|Problem 44: Approximating LIS Length in the Streaming Model]]
+
*{{ProblemLink|44}}
*[[Open_Problems:45|Problem 45: Streaming Max-Cut/Max-CSP]]
+
*{{ProblemLink|45}}
*[[Open_Problems:46|Problem 46: Fast JL Transform  for Sparse Vectors]]
+
*{{ProblemLink|46}}
*[[Open_Problems:47|Problem 47: Annotated Streaming]]
+
*{{ProblemLink|47}}
*[[Open_Problems:48|Problem 48: Sketching Shift Metrics]]
+
*{{ProblemLink|48}}
*[[Open_Problems:49|Problem 49: Sketching Earth Mover Distance]]
+
*{{ProblemLink|49}}
*[[Open_Problems:50|Problem 50: Sparse Recovery for Tree Models]]
+
*{{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]]:
*[[Open_Problems:51|Problem 51: “For All” Guarantee for Computationally Bounded Adversaries]]
+
*{{ProblemLink|51}}
*[[Open_Problems:52|Problem 52: TSP in the Streaming Model]]
+
*{{ProblemLink|52}}
*[[Open_Problems:53|Problem 53: Homomorphic Hash Functions]]
+
*{{ProblemLink|53}}
*[[Open_Problems:54|Problem 54: Faster JL Dimensionality Reduction]]
+
*{{ProblemLink|54}}
*[[Open_Problems:55|Problem 55: Applications of Clifford Algebras in Streaming]]
+
*{{ProblemLink|55}}
*[[Open_Problems:56|Problem 56: Efficient Measures of “Surprisingness” of Sequences]]
+
*{{ProblemLink|56}}
*[[Open_Problems:57|Problem 57: Coding Theory in the Streaming Model]]
+
*{{ProblemLink|57}}
*[[Open_Problems:58|Problem 58: Signatures for Set Equality]]
+
*{{ProblemLink|58}}
*[[Open_Problems:59|Problem 59: Low Expansion Encoding of Edit Distance]]
+
*{{ProblemLink|59}}
*[[Open_Problems:60|Problem 60: Single-Pass Unweighted Matchings]]
+
*{{ProblemLink|60}}
 +
 
 +
Problems suggested at the [[Workshops:Bertinoro_2014|Bertinoro Workshop on Sublinear Algorithms 2014]]:
 +
*{{ProblemLink|61}}
 +
*{{ProblemLink|62}}
 +
*{{ProblemLink|63}}
 +
*{{ProblemLink|64}}
 +
*{{ProblemLink|65}}
 +
*{{ProblemLink|66}}
 +
*{{ProblemLink|67}}
 +
*{{ProblemLink|68}}
 +
 
 +
Problems suggested at the [[Workshops:Baltimore_2016|Sublinear Algorithms Workshop 2016 at Johns Hopkins University]]:
 +
*{{ProblemLink|69}}
 +
*{{ProblemLink|70}}
 +
*{{ProblemLink|71}}
 +
*{{ProblemLink|72}}
 +
*{{ProblemLink|73}}
 +
*{{ProblemLink|74}}
 +
 
 +
Problems suggested at the [[Workshops:Banff_2017|Workshop on Communication Complexity and Applications 2017 at the Banff International Research Station]]:
 +
*{{ProblemLink|75}}
 +
*{{ProblemLink|76}}
 +
*{{ProblemLink|77}}
 +
*{{ProblemLink|78}}
 +
*{{ProblemLink|79}}
 +
*{{ProblemLink|80}}
 +
 
 +
Problems suggested at the [[Workshops:FOCS 2017|Frontiers in Distribution Testing workshop at FOCS 2017]]:
 +
*{{ProblemLink|81}}
 +
*{{ProblemLink|82}}
 +
*{{ProblemLink|83}}
 +
*{{ProblemLink|84}}
 +
*{{ProblemLink|85}}
 +
*{{ProblemLink|86}}
 +
*{{ProblemLink|87}}
 +
*{{ProblemLink|88}}
 +
*{{ProblemLink|89}}

Revision as of 06:29, 8 November 2017

Problems suggested at the IITK Workshop on Algorithms for Data Streams 2006:

Problems suggested at the IITK Workshop on Algorithms for Processing Massive Data Sets 2009:

Problems suggested at the Bertinoro Workshop on Sublinear Algorithms 2011:

Problems suggested at the Dortmund Workshop on Algorithms for Data Streams 2012:

Problems suggested at the Bertinoro Workshop on Sublinear Algorithms 2014:

Problems suggested at the Sublinear Algorithms Workshop 2016 at Johns Hopkins University:

Problems suggested at the Workshop on Communication Complexity and Applications 2017 at the Banff International Research Station:

Problems suggested at the Frontiers in Distribution Testing workshop at FOCS 2017: