Open Problems:66 - Revision history

Gautam Kamath at 19:20, 7 November 2018

2018-11-07T19:20:53Z

Gautam Kamath at 19:20, 7 November 2018

2018-11-07T19:20:24Z

Krzysztof Onak: Added missing citation

2015-06-19T20:01:23Z

Added missing citation

Krzysztof Onak: Please add citation!

2015-05-21T13:44:17Z

Please add citation!

18.189.42.114 at 23:10, 20 May 2015

2015-05-20T23:10:50Z

Krzysztof Onak at 19:47, 12 December 2014

2014-12-12T19:47:28Z

Krzysztof Onak at 19:41, 12 December 2014

2014-12-12T19:41:16Z

Gautam Kamath at 00:13, 9 December 2014

2014-12-09T00:13:22Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Eldar Fischer to Open Problems:66

2014-06-13T23:01:38Z

Krzysztof Onak moved page Waiting:Eldar Fischer to Open Problems:66

Krzysztof Onak at 23:01, 13 June 2014

2014-06-13T23:01:13Z

← Older revision		Revision as of 19:20, 7 November 2018
Line 13:		Line 13:
	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh {{cite\|FalahatgarJOPS-15}} showed that $O\left(\frac{\log{\log{n}}}{\epsilon^5}\right)$ queries are sufficient. This determines the query complexity of the problem up to a factor of $\sqrt{\log \log n}$.		Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh {{cite\|FalahatgarJOPS-15}} showed that $O\left(\frac{\log{\log{n}}}{\epsilon^5}\right)$ queries are sufficient. This determines the query complexity of the problem up to a factor of $\sqrt{\log \log n}$.

−	In the non-adaptive model, Kamath and Tzamos {{cite\|KamathT-19}} showed that $\poly \log n$ conditional queries are sufficient for equivalence testing. A lower bound of $\Omega(\log n)$ by Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} for uniformity testing shows that identity and equivalence testing have complexities related by polynomial factors in the non-adaptive model, compared to the gap in the adaptive model.	+	In the non-adaptive model, Kamath and Tzamos {{cite\|KamathT-19}} showed that $\operatorname{poly} \log n$ conditional queries are sufficient for equivalence testing. A lower bound of $\Omega(\log n)$ by Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} for uniformity testing shows that identity and equivalence testing have complexities related by polynomial factors in the non-adaptive model, compared to the gap in the adaptive model.

← Older revision		Revision as of 19:20, 7 November 2018
Line 12:		Line 12:
	==Updates==		==Updates==
	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh {{cite\|FalahatgarJOPS-15}} showed that $O\left(\frac{\log{\log{n}}}{\epsilon^5}\right)$ queries are sufficient. This determines the query complexity of the problem up to a factor of $\sqrt{\log \log n}$.		Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh {{cite\|FalahatgarJOPS-15}} showed that $O\left(\frac{\log{\log{n}}}{\epsilon^5}\right)$ queries are sufficient. This determines the query complexity of the problem up to a factor of $\sqrt{\log \log n}$.
		+
		+	In the non-adaptive model, Kamath and Tzamos {{cite\|KamathT-19}} showed that $\poly \log n$ conditional queries are sufficient for equivalence testing. A lower bound of $\Omega(\log n)$ by Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} for uniformity testing shows that identity and equivalence testing have complexities related by polynomial factors in the non-adaptive model, compared to the gap in the adaptive model.

← Older revision		Revision as of 20:01, 19 June 2015
Line 11:		Line 11:

	==Updates==		==Updates==
−	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. ~~Concurrently, in 2015,~~ Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh~~<span style="color:red"><sup>(citation missing)</sup></span>~~ showed that $O(\frac{\log{\log{n}}}{\~~varepsilon~~^5})$ queries are sufficient~~, so that~~ the query complexity of ~~this~~ problem ~~is determined~~ up to a factor of $\sqrt{\log \log n}$.	+	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh {{cite\|FalahatgarJOPS-15}} showed that $O\left(\frac{\log{\log{n}}}{\epsilon^5}\right)$ queries are sufficient. This determines the query complexity of the problem up to a factor of $\sqrt{\log \log n}$.

@@ Line 10: / Line 10: @@
 What can we say if both distributions are unknown? The best known upper bound is $\tilde O\left( \frac{\log^5 n}{\epsilon^4} \right)$ {{cite|CanonneRS-14}}.
-==Update==
+==Updates==
-Acharya, Canonne, and Kamath {{cite|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Concurrently, in 2015, Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh showed that $O(\frac{\log{\log{n}}}{\varepsilon^5})$ queries are sufficient, so that the query complexity of this problem is determined up to a factor of $\sqrt{\log \log n}$.
+Acharya, Canonne, and Kamath {{cite|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Concurrently, in 2015, Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh<span style="color:red"><sup>(citation missing)</sup></span> showed that $O(\frac{\log{\log{n}}}{\varepsilon^5})$ queries are sufficient, so that the query complexity of this problem is determined up to a factor of $\sqrt{\log \log n}$.

← Older revision		Revision as of 23:10, 20 May 2015
Line 11:		Line 11:

	==Update==		==Update==
−	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$.	+	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$. Concurrently, in 2015, Falahatgar, Jafarpour, Orlitsky, Pichapathi, and Suresh showed that $O(\frac{\log{\log{n}}}{\varepsilon^5})$ queries are sufficient, so that the query complexity of this problem is determined up to a factor of $\sqrt{\log \log n}$.

← Older revision		Revision as of 19:47, 12 December 2014
Line 11:		Line 11:

	==Update==		==Update==
−	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. ~~This implies that~~ the case of ~~two~~ unknown distributions ~~requires a~~ number of queries ~~that~~ is a function of $n$.	+	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. Contrary to the case of only one distribution unknown, if both distributions are unknown, the required number of queries is a function of $n$.

← Older revision		Revision as of 19:41, 12 December 2014
Line 11:		Line 11:

	==Update==		==Update==
−	~~It was shown by~~ Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} that~~, for a constant $\epsilon > 0$,~~ $\Omega(\sqrt{\log \log n})$ conditional queries are needed ~~to test equivalence if both~~ distributions ~~are unknown~~.	+	Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} showed that $\Omega(\sqrt{\log \log n})$ conditional queries are needed in this case for some constant $\epsilon > 0$. This implies that the case of two unknown distributions requires a number of queries that is a function of $n$.

← Older revision		Revision as of 00:13, 9 December 2014
Line 9:		Line 9:

	What can we say if both distributions are unknown? The best known upper bound is $\tilde O\left( \frac{\log^5 n}{\epsilon^4} \right)$ {{cite\|CanonneRS-14}}.		What can we say if both distributions are unknown? The best known upper bound is $\tilde O\left( \frac{\log^5 n}{\epsilon^4} \right)$ {{cite\|CanonneRS-14}}.
		+
		+	==Update==
		+	It was shown by Acharya, Canonne, and Kamath {{cite\|AcharyaCK-14}} that, for a constant $\epsilon > 0$, $\Omega(\sqrt{\log \log n})$ conditional queries are needed to test equivalence if both distributions are unknown.

← Older revision	Revision as of 23:01, 13 June 2014
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro14
 |who=Eldar Fischer