ECCC-Report TR13-056https://eccc.weizmann.ac.il/report/2013/056Comments and Revisions published for TR13-056en-usThu, 23 Jun 2016 14:14:04 +0300
Revision 5
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056#revision5We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Thu, 23 Jun 2016 14:14:04 +0300https://eccc.weizmann.ac.il/report/2013/056#revision5
Revision 4
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056#revision4We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Wed, 02 Mar 2016 19:44:07 +0200https://eccc.weizmann.ac.il/report/2013/056#revision4
Revision 3
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056#revision3We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Wed, 30 Sep 2015 16:08:23 +0300https://eccc.weizmann.ac.il/report/2013/056#revision3
Revision 2
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056#revision2We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Thu, 21 Nov 2013 20:57:04 +0200https://eccc.weizmann.ac.il/report/2013/056#revision2
Revision 1
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056#revision1We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Fri, 06 Sep 2013 19:03:19 +0300https://eccc.weizmann.ac.il/report/2013/056#revision1
Paper TR13-056
| Common information and unique disjointness |
Gábor Braun,
Sebastian Pokutta
https://eccc.weizmann.ac.il/report/2013/056We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally and improve previous results by Braverman and Moitra [2012] in terms of being (almost) optimal. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis’ Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in Braun et al. [2012] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef et al. [2004]. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.Fri, 05 Apr 2013 18:11:33 +0300https://eccc.weizmann.ac.il/report/2013/056