User contributions
- 20:40, 26 August 2019 (diff | hist) . . (0) . . Open Problems:95 (current)
- 20:06, 26 August 2019 (diff | hist) . . (0) . . Workshops:WOLA 2019 (current)
- 04:32, 20 August 2019 (diff | hist) . . (-1) . . Open Problems:91 (current)
- 04:31, 20 August 2019 (diff | hist) . . (0) . . Open Problems:90 (current)
- 22:13, 7 August 2019 (diff | hist) . . (+36) . . Open Problems:94
- 22:11, 7 August 2019 (diff | hist) . . (+1,587) . . N Open Problems:94 (Created page with "{{Header |title=Ads, Impressions, and Statistics&action=submit |source=warwick18 }} 1. Consider the problem of reporting statistics about online ads to the advertisers that...")
- 22:07, 7 August 2019 (diff | hist) . . (-1) . . Waiting
- 22:07, 7 August 2019 (diff | hist) . . (+45) . . Waiting
- 22:06, 7 August 2019 (diff | hist) . . (+120) . . Open Problems:93
- 22:05, 7 August 2019 (diff | hist) . . (+152) . . Bibliography
- 22:03, 7 August 2019 (diff | hist) . . (+943) . . N Open Problems:93 (Created page with "The model of Local Differential Privacy (LDP) asks for protocols for information release, so that each user's output meets a differential privacy guarantee. A basic primitive...")
- 21:59, 7 August 2019 (diff | hist) . . (+59) . . Waiting
- 21:57, 7 August 2019 (diff | hist) . . (+1,057) . . N Open Problems:92 (Created page with "{{Header |title=Streaming Algorithms for Approximating the Number of $H$-Subgraphs |source=warwick18 |who=He Sun }} Designing a streaming algorithm that approximately computes...")
- 21:54, 7 August 2019 (diff | hist) . . (-4) . . Waiting
- 21:54, 7 August 2019 (diff | hist) . . (+80) . . Waiting
- 21:47, 7 August 2019 (diff | hist) . . (+1,130) . . N Open Problems:102 (Created page with "{{Header |title=Making edges happy in the LOCAL model |source=wola19 |who=Jukka Suomela }} In this question, the input is the underlying graph $G=(V,E)$, promised to have max...")
- 21:45, 7 August 2019 (diff | hist) . . (-13) . . Open Problems:101
- 21:44, 7 August 2019 (diff | hist) . . (0) . . Bibliography
- 21:43, 7 August 2019 (diff | hist) . . (+668) . . Bibliography
- 21:40, 7 August 2019 (diff | hist) . . (+715) . . N Open Problems:101 (Created page with "{{Header |title=Effective Support Size Estimation in the Dual Model |source=wola19 |who=Sorrachai Yingchareonthawornchai }} In this question, the input is the underlying grap...")
- 21:37, 7 August 2019 (diff | hist) . . (0) . . Bibliography
- 21:37, 7 August 2019 (diff | hist) . . (+1,891) . . N Open Problems:100 (Created page with "{{Header |title=Effective Support Size Estimation in the Dual Model |source=wola19 |who=Oded Goldreich }} For a probability distribution $p$ over a discrete domain $\Omega$, a...")
- 21:37, 7 August 2019 (diff | hist) . . (+180) . . Bibliography
- 21:35, 7 August 2019 (diff | hist) . . (+4) . . Open Problems:98
- 21:35, 7 August 2019 (diff | hist) . . (+1) . . Open Problems:99
- 21:30, 7 August 2019 (diff | hist) . . (+15) . . Open Problems:98
- 21:30, 7 August 2019 (diff | hist) . . (+1) . . Open Problems:99
- 21:29, 7 August 2019 (diff | hist) . . (-44) . . Open Problems:99
- 21:28, 7 August 2019 (diff | hist) . . (+1,363) . . N Open Problems:99 (Created page with "{{Header |title=Vertex-Distribution-Free Graph Testing |source=wola19 |who=Oded Goldreich }} The graph query model where one gets to query vertices uniformly at random, as men...")
- 21:28, 7 August 2019 (diff | hist) . . (+134) . . Bibliography
- 21:27, 7 August 2019 (diff | hist) . . (+179) . . Bibliography
- 21:20, 7 August 2019 (diff | hist) . . (-1) . . Bibliography
- 21:20, 7 August 2019 (diff | hist) . . (0) . . Bibliography
- 21:19, 7 August 2019 (diff | hist) . . (+227) . . Bibliography
- 21:18, 7 August 2019 (diff | hist) . . (+1,637) . . N Open Problems:98 (Created page with "{{Header |title=Estimating a Graph's Degree Distribution |source=wola19 |who=C. Seshadhri }} The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree fr...")
- 21:14, 7 August 2019 (diff | hist) . . (+620) . . N Open Problems:97 (Created page with "{{Header |title=Local Computation Algorithm for MIS |source=wola19 |who=Mohsen Gaffhari }} In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$,...")
- 20:38, 7 August 2019 (diff | hist) . . (+91) . . Open Problems:96
- 20:36, 7 August 2019 (diff | hist) . . (+1,812) . . N Open Problems:96 (Created page with "Given a distance parameter $\varepsilon\in(0,1]$, i.i.d. samples from an unknown distribution $p$ and a (known) reference distribution $q$, both over $[n] = \{1,\dots,n\}$, th...")
- 20:36, 7 August 2019 (diff | hist) . . (+2) . . Bibliography
- 20:35, 7 August 2019 (diff | hist) . . (+191) . . Bibliography
- 20:26, 7 August 2019 (diff | hist) . . (+743) . . N Open Problems:95 (Created page with "{{Header |title=Non-Adaptive Group Testing |source=wola19 |who=Oliver Gebhard }} In (non-adaptive) quantitative group testing, one has a population of $n$ individuals, among w...")
- 20:15, 7 August 2019 (diff | hist) . . (+421) . . Waiting
- 20:04, 27 March 2018 (diff | hist) . . (-8) . . Open Problems:90
- 20:03, 27 March 2018 (diff | hist) . . (+2,165) . . N Open Problems:90 (Created page with "{{Header |title=Dense Graph Property Testing "Tradeoffs" |source=online |who=Clement Canonne }} In the dense graph model of property testing (where the testing algorithm is g...")
- 03:01, 2 November 2017 (diff | hist) . . (-148) . . Waiting
- 23:24, 25 October 2017 (diff | hist) . . (+2) . . Open Problems:87
- 22:57, 25 October 2017 (diff | hist) . . (-1) . . Open Problems:87
- 22:57, 25 October 2017 (diff | hist) . . (+732) . . N Open Problems:87 (Created page with "{{Header |source=focs17 |who=Gautam Kamath |title=Equivalence testing with conditional samples }} ''This is a continuation of this previous open problem...")
- 22:30, 25 October 2017 (diff | hist) . . (+119) . . Bibliography
- 22:29, 25 October 2017 (diff | hist) . . (+1,887) . . N Open Problems:88 (Created page with "{{Header |source=focs17 |who=Clément Canonne |title=Separating PDF and CDF query models }} Recall that in the ''dual'' and ''cumulative dual'' models of distribution testing...")
- 22:09, 25 October 2017 (diff | hist) . . (+47) . . Open Problems:86
- 22:09, 25 October 2017 (diff | hist) . . (+174) . . Open Problems:86
- 22:07, 25 October 2017 (diff | hist) . . (-1) . . Open Problems:86
- 22:07, 25 October 2017 (diff | hist) . . (+1,120) . . N Open Problems:86 (Created page with "{{Header |title=Equivalence testing lower bound via communication complexity |source=focs17 |who=Clément Canonne }} Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently descr...")
- 21:56, 25 October 2017 (diff | hist) . . (+6) . . Open Problems:84
- 21:55, 25 October 2017 (diff | hist) . . (0) . . Open Problems:84
- 21:55, 25 October 2017 (diff | hist) . . (0) . . Waiting
- 21:08, 25 October 2017 (diff | hist) . . (-1) . . Bibliography
- 21:07, 25 October 2017 (diff | hist) . . (-17) . . Bibliography
- 21:07, 25 October 2017 (diff | hist) . . (+223) . . Bibliography
- 21:03, 25 October 2017 (diff | hist) . . (+130) . . Open Problems:84
- 21:01, 25 October 2017 (diff | hist) . . (+1,522) . . N Open Problems:84 (Created page with "{{Header |source=focs17 |who=Alon Orlitsky |title=Efficient Pattern Maximum Likelihood Computation }} Given a sequence of samples $\mathbf{s}=(s_1,\dots,s_n)\in\mathbb{N}^n$,...")
- 18:47, 25 October 2017 (diff | hist) . . (+178) . . Bibliography
- 18:44, 25 October 2017 (diff | hist) . . (+8) . . Open Problems:89
- 18:44, 25 October 2017 (diff | hist) . . (0) . . Waiting
- 18:43, 25 October 2017 (diff | hist) . . (+2,119) . . N Open Problems:89 (Created page with "{{Header |source=focs17 |who=Tom Gur |title=AM vs. NP for proofs of proximity in distribution testing }} ''Proofs of proximity for properties of distributions'' [ChiesaG17]...")
- 21:24, 23 October 2017 (diff | hist) . . (+1) . . Waiting
- 21:24, 23 October 2017 (diff | hist) . . (+6) . . Open Problems:83
- 20:12, 20 October 2017 (diff | hist) . . (-8) . . Waiting
- 20:12, 20 October 2017 (diff | hist) . . (+422) . . Waiting
- 19:58, 20 October 2017 (diff | hist) . . (-1) . . Open Problems:85
- 19:58, 20 October 2017 (diff | hist) . . (+672) . . N Open Problems:85 (Created page with "{{Header |source=focs17 |who=Ryan O'Donnell |title=Sample Stretching }} Let $p$ be an unknown (discrete) probability distribution over a discrete domain $\Omega$ (e.g., $\Ome...")
- 19:50, 20 October 2017 (diff | hist) . . (+162) . . Waiting
- 18:52, 20 October 2017 (diff | hist) . . (+485) . . Bibliography
- 18:48, 20 October 2017 (diff | hist) . . (+102) . . Open Problems:83
- 18:46, 20 October 2017 (diff | hist) . . (+2,871) . . N Open Problems:83 (Created page with "{{Header |title=Instance-optimal Hellinger testing |source=focs17 |who=Clément Canonne }} Given the full description of a fixed distribution $q$ over a discrete domain (say $...")
- 18:23, 20 October 2017 (diff | hist) . . (+2) . . Open Problems:82
- 18:22, 20 October 2017 (diff | hist) . . (+40) . . Open Problems:82
- 18:22, 20 October 2017 (diff | hist) . . (+136) . . Waiting
- 18:19, 20 October 2017 (diff | hist) . . (0) . . Waiting
- 18:19, 20 October 2017 (diff | hist) . . (+84) . . Waiting
- 18:17, 20 October 2017 (diff | hist) . . (+1) . . Bibliography
- 18:16, 20 October 2017 (diff | hist) . . (+114) . . Bibliography
- 18:13, 20 October 2017 (diff | hist) . . (+9) . . Open Problems:82
- 18:10, 20 October 2017 (diff | hist) . . (+1,526) . . N Open Problems:82 (Created page with "{{Header |title=Beyond identity testing |source=focs17 |who=Clément Canonne }} Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete...")
- 17:55, 20 October 2017 (diff | hist) . . (+62) . . Waiting
- 05:08, 20 October 2017 (diff | hist) . . (+5) . . Open Problems:81
- 05:06, 20 October 2017 (diff | hist) . . (+3) . . Open Problems:81
- 05:06, 20 October 2017 (diff | hist) . . (+2) . . Waiting
- 05:05, 20 October 2017 (diff | hist) . . (+1) . . Bibliography
- 05:05, 20 October 2017 (diff | hist) . . (+240) . . Bibliography
- 05:02, 20 October 2017 (diff | hist) . . (+33) . . Open Problems:81
- 05:01, 20 October 2017 (diff | hist) . . (+869) . . N Open Problems:81 (Created page with "{{Header |source=focs17 |who=Jayadev Acharya }} For any $\alpha \geq 0$, the ''Rényi entropy of order $\alpha$'' of a probability distribution $p$ over a discrete domain $\Om...")
- 04:50, 20 October 2017 (diff | hist) . . (+64) . . Waiting
- 04:48, 20 October 2017 (diff | hist) . . (+8) . . Open Problems:By Number
- 04:45, 20 October 2017 (diff | hist) . . (+128) . . Open Problems:By Number
- 16:06, 15 October 2017 (diff | hist) . . (+414) . . N Workshops:FOCS 2017 (Created page with "{{DISPLAYTITLE:Frontiers in Distribution Testing at FOCS 2017}} The workshop was held at FOCS in Berkeley, USA, in November 2017. This list contains open problems suggested by...")
- 16:49, 16 January 2016 (diff | hist) . . (+88) . . Bibliography
- 16:41, 16 January 2016 (diff | hist) . . (+259) . . Bibliography
- 16:38, 16 January 2016 (diff | hist) . . (+180) . . Bibliography
- 16:35, 16 January 2016 (diff | hist) . . (+186) . . Bibliography
- 16:33, 16 January 2016 (diff | hist) . . (0) . . m Open Problems:74
- 16:32, 16 January 2016 (diff | hist) . . (+791) . . Open Problems:74
- 15:40, 13 January 2016 (diff | hist) . . (+13) . . Waiting
- 18:09, 12 January 2016 (diff | hist) . . (+16) . . Open Problems:74
- 02:50, 12 January 2016 (diff | hist) . . (+1) . . Open Problems:71
- 02:49, 12 January 2016 (diff | hist) . . (-4) . . Open Problems:71
- 02:39, 12 January 2016 (diff | hist) . . (+20) . . Waiting
- 02:38, 12 January 2016 (diff | hist) . . (+38) . . N Open Problems talk:71 (Created page with "Clément: check and fill in citations.")
- 02:38, 12 January 2016 (diff | hist) . . (0) . . Open Problems:71
- 02:38, 12 January 2016 (diff | hist) . . (+192) . . Bibliography
- 02:34, 12 January 2016 (diff | hist) . . (+917) . . Open Problems:71
- 02:03, 12 January 2016 (diff | hist) . . (+1) . . Open Problems:73
- 02:01, 12 January 2016 (diff | hist) . . (+13) . . Waiting
- 02:01, 12 January 2016 (diff | hist) . . (+7) . . Bibliography
- 02:00, 12 January 2016 (diff | hist) . . (+152) . . Bibliography
- 01:58, 12 January 2016 (diff | hist) . . (+1,202) . . Open Problems:73
- 22:19, 10 January 2016 (diff | hist) . . (+39) . . Waiting
- 22:18, 10 January 2016 (diff | hist) . . (0) . . Bibliography
- 22:17, 10 January 2016 (diff | hist) . . (+357) . . Bibliography
- 22:13, 10 January 2016 (diff | hist) . . (+16) . . Open Problems:69
- 22:13, 10 January 2016 (diff | hist) . . (+26) . . Open Problems:69
- 22:12, 10 January 2016 (diff | hist) . . (+439) . . Open Problems:69
- 22:08, 10 January 2016 (diff | hist) . . (+1,754) . . Open Problems:69
- 21:37, 10 January 2016 (diff | hist) . . (+1) . . Bibliography
- 21:36, 10 January 2016 (diff | hist) . . (+3) . . Bibliography
- 21:36, 10 January 2016 (diff | hist) . . (0) . . Open Problems:70
- 21:35, 10 January 2016 (diff | hist) . . (+164) . . Bibliography
- 21:32, 10 January 2016 (diff | hist) . . (+1,297) . . N Open Problems:70 (Created page with "{{Header |title=Open Problems in $L_p$-Testing |source=baltimore16 |who=Grigory Yaroslavtsev }} Extending the usual setting of property testing to functions $f\colon\{1,\dots...")
- 21:09, 10 January 2016 (diff | hist) . . (+29) . . Waiting
- 21:07, 10 January 2016 (diff | hist) . . (+13) . . Open Problems talk:72
- 21:07, 10 January 2016 (diff | hist) . . (+250) . . N Open Problems talk:72 (Created page with "Clément: Not clear to me from glancing at the paper (http://homes.soic.indiana.edu/qzhangcs/papers/pods15-join.pdf, Section 3.1) if $C$ is a Boolean matrix or an integer-valu...")
- 21:05, 10 January 2016 (diff | hist) . . (+43) . . Open Problems:72
- 21:04, 10 January 2016 (diff | hist) . . (+227) . . Bibliography
- 21:02, 10 January 2016 (diff | hist) . . (+886) . . Open Problems:72
- 11:46, 17 June 2015 (diff | hist) . . (-1) . . m Resources (Fixed typos in names.)