News
Aug 28, 2019: Open problems from two workshops have been posted: the 2018 Workshop on Data Summarization at the University of Warwick and the 3rd Workshop on Local Algorithms at ETH Zurich.
Jun 13, 2019: The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at admin@sublinear.info if you notice any problems.
Nov 08, 2017: A list of open problems from Frontiers in Distribution Testing, a workshop at FOCS 2017, has been posted.
Apr 28, 2017: A list of open problems from a BIRS workshop on communication complexity has been posted.
Jan 19, 2017: We made the switch to HTTPS for more security. Please let us know at admin@sublinear.info if something stops to work. Consider also updating your password.
Dec 13, 2016: The webpage has been updated to the 1.27 branch of MediaWiki. Please email us at admin@sublinear.info if you notice any problems.
May 26, 2016: The webpage has been updated and math rendering should work correctly again. Please email us at admin@sublinear.info if you notice any problems.
May 21, 2016: The latest security update of MediaWiki unfortunately broke the extension responsible for rendering math equations. We turned it off for now. Versions of the problems with correctly rendered math can be enjoyed in the pdf form.
Jan 18, 2016: Open problems from the Sublinear Algorithms Workshop at the Johns Hopkins University have been posted.
May 09, 2015: The entire list is now available as a single pdf. Checking the online version is still recommended. The pdf may become outdated and we can't promise prompt updates.
May 07, 2015: The wiki has just been updated to MediaWiki 1.23, the current long term support release. Please notify us at admin@sublinear.info if anything stops working.
Jun 13, 2014: Open problems from the 2014 Bertinoro Workshop on Sublinear Algorithms have been posted.
Sep 21, 2013: Eric Blais, Sourav Chakraborty, and C. Seshadhri have started Property Testing Review, a blog dedicated to new developments in property testing and sublinear-time algorithms.
May 20, 2013: Recently submitted updates:
Mar 29, 2013: Recently submitted updates:
- Problem 31: Gap-Hamming Information Cost (resolved)
- Problem 38: Query Complexity of Local Partitioning Oracles
- Problem 40: Testing Monotonicity and the Lipschitz Property (resolved)
Feb 10, 2013: A simple anti-spam solution has been installed. Email confirmation is no longer required to edit the wiki, but we suggest that you still log in if you don't want your IP address to be displayed in the edit history.
Dec 12, 2012: The wiki is now officially open to celebrate 12/12/12!
Nov 10, 2012: Email confirmation is now required to prevent spammers.
Oct 01, 2012: This website will contain a list of open problems. There will be an official opening soon! Stay tuned!
