1 resultado para Alternative and Supplementary Communication
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- JISC Information Environment Repository (1)
- Repository Napier (1)
- ABACUS. Repositorio de Producción Científica - Universidad Europea (2)
- Aberystwyth University Repository - Reino Unido (1)
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (1)
- Adam Mickiewicz University Repository (4)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (6)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (1)
- Aquatic Commons (7)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (1)
- Archive of European Integration (41)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (6)
- Aston University Research Archive (26)
- B-Digital - Universidade Fernando Pessoa - Portugal (3)
- Biblioteca de Teses e Dissertações da USP (3)
- Biblioteca Digital da Câmara dos Deputados (2)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (5)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (1)
- Biblioteca Digital de la Universidad Católica Argentina (2)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (16)
- Bioline International (1)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (27)
- Boston University Digital Common (4)
- Brock University, Canada (6)
- Bulgarian Digital Mathematics Library at IMI-BAS (3)
- CaltechTHESIS (2)
- Cambridge University Engineering Department Publications Database (9)
- CentAUR: Central Archive University of Reading - UK (25)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (24)
- Cochin University of Science & Technology (CUSAT), India (3)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (1)
- CORA - Cork Open Research Archive - University College Cork - Ireland (1)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (3)
- CUNY Academic Works (2)
- Dalarna University College Electronic Archive (10)
- Deakin Research Online - Australia (85)
- Department of Computer Science E-Repository - King's College London, Strand, London (1)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Commons - Michigan Tech (6)
- Digital Commons @ DU | University of Denver Research (2)
- Digital Commons at Florida International University (10)
- DigitalCommons@The Texas Medical Center (10)
- DigitalCommons@University of Nebraska - Lincoln (4)
- Doria (National Library of Finland DSpace Services) - National Library of Finland, Finland (2)
- DRUM (Digital Repository at the University of Maryland) (6)
- Duke University (11)
- Ecology and Society (2)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (9)
- Glasgow Theses Service (1)
- Greenwich Academic Literature Archive - UK (5)
- Helda - Digital Repository of University of Helsinki (17)
- Indian Institute of Science - Bangalore - Índia (19)
- Instituto Politécnico de Viseu (2)
- Instituto Politécnico do Porto, Portugal (12)
- Instituto Superior de Psicologia Aplicada - Lisboa (2)
- Iowa Publications Online (IPO) - State Library, State of Iowa (Iowa), United States (1)
- Massachusetts Institute of Technology (1)
- Memoria Académica - FaHCE, UNLP - Argentina (3)
- National Center for Biotechnology Information - NCBI (3)
- Nottingham eTheses (1)
- Portal de Revistas Científicas Complutenses - Espanha (14)
- Publishing Network for Geoscientific & Environmental Data (2)
- QSpace: Queen's University - Canada (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (54)
- Queensland University of Technology - ePrints Archive (197)
- ReCiL - Repositório Científico Lusófona - Grupo Lusófona, Portugal (1)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (11)
- Repositório digital da Fundação Getúlio Vargas - FGV (2)
- Repositório Institucional da Universidade de Aveiro - Portugal (13)
- Repositorio Institucional de la Universidad de Málaga (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (28)
- Repositorio Institucional Universidad de Medellín (1)
- Research Open Access Repository of the University of East London. (1)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (4)
- SAPIENTIA - Universidade do Algarve - Portugal (2)
- School of Medicine, Washington University, United States (2)
- Universidad de Alicante (5)
- Universidad del Rosario, Colombia (1)
- Universidad Politécnica de Madrid (18)
- Universidade Complutense de Madrid (1)
- Universidade de Lisboa - Repositório Aberto (1)
- Universidade Federal do Pará (1)
- Universidade Federal do Rio Grande do Norte (UFRN) (5)
- Universidade Metodista de São Paulo (3)
- Universita di Parma (1)
- Universitat de Girona, Spain (2)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (1)
- Université de Lausanne, Switzerland (1)
- Université de Montréal (2)
- Université de Montréal, Canada (8)
- Université Laval Mémoires et thèses électroniques (1)
- University of Connecticut - USA (3)
- University of Michigan (31)
- University of Queensland eSpace - Australia (19)
- University of Washington (3)
- WestminsterResearch - UK (6)
Resumo:
An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.