1 resultado para limits of visual detection
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- ABACUS. Repositorio de Producción Científica - Universidad Europea (1)
- Aberdeen University (1)
- Abertay Research Collections - Abertay University’s repository (1)
- Aberystwyth University Repository - Reino Unido (2)
- Academic Archive On-line (Jönköping University; Sweden) (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (1)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (1)
- Aquatic Commons (4)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (4)
- Archive of European Integration (6)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (3)
- Aston University Research Archive (49)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (6)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (4)
- Bioline International (1)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (59)
- Boston University Digital Common (12)
- Brock University, Canada (3)
- Brunel University (1)
- Bucknell University Digital Commons - Pensilvania - USA (3)
- CaltechTHESIS (5)
- Cambridge University Engineering Department Publications Database (30)
- CentAUR: Central Archive University of Reading - UK (42)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (57)
- Cochin University of Science & Technology (CUSAT), India (2)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (3)
- CORA - Cork Open Research Archive - University College Cork - Ireland (4)
- Dalarna University College Electronic Archive (2)
- Deakin Research Online - Australia (73)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Archives@Colby (3)
- Digital Commons - Michigan Tech (3)
- Digital Commons @ DU | University of Denver Research (2)
- Digital Commons at Florida International University (13)
- Digital Peer Publishing (1)
- Digital Repository at Iowa State University (1)
- DigitalCommons@The Texas Medical Center (1)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (15)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (5)
- Greenwich Academic Literature Archive - UK (5)
- Helda - Digital Repository of University of Helsinki (16)
- Hospitais da Universidade de Coimbra (1)
- Indian Institute of Science - Bangalore - Índia (31)
- Institutional Repository of Leibniz University Hannover (1)
- Instituto Politécnico do Porto, Portugal (2)
- Massachusetts Institute of Technology (6)
- Memoria Académica - FaHCE, UNLP - Argentina (3)
- Memorial University Research Repository (10)
- National Center for Biotechnology Information - NCBI (12)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (5)
- Portal de Revistas Científicas Complutenses - Espanha (4)
- Publishing Network for Geoscientific & Environmental Data (6)
- QSpace: Queen's University - Canada (2)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (118)
- Queensland University of Technology - ePrints Archive (121)
- ReCiL - Repositório Científico Lusófona - Grupo Lusófona, Portugal (1)
- Repositório Científico da Universidade de Évora - Portugal (2)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (3)
- Repositório digital da Fundação Getúlio Vargas - FGV (3)
- Repositório Institucional da Universidade de Aveiro - Portugal (1)
- Repositório Institucional dos Hospitais da Universidade Coimbra (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (39)
- Research Open Access Repository of the University of East London. (2)
- SAPIENTIA - Universidade do Algarve - Portugal (1)
- School of Medicine, Washington University, United States (4)
- Scielo España (1)
- Scientific Open-access Literature Archive and Repository (1)
- Universidad de Alicante (2)
- Universidad Politécnica de Madrid (10)
- Universidade Complutense de Madrid (2)
- Universidade Federal do Pará (2)
- Universidade Federal do Rio Grande do Norte (UFRN) (1)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (2)
- Université de Lausanne, Switzerland (5)
- Université de Montréal (2)
- Université de Montréal, Canada (5)
- University of Michigan (27)
- University of Queensland eSpace - Australia (22)
- University of Washington (3)
- WestminsterResearch - UK (5)
- Worcester Research and Publications - Worcester Research and Publications - UK (1)
Resumo:
We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n1/2-ε)-approximations for CLIQUE require LPs of size 2nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.