1 resultado para Tail-approximation
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- KUPS-Datenbank - Universität zu Köln - Kölner UniversitätsPublikationsServer (1)
- ABACUS. Repositorio de Producción Científica - Universidad Europea (1)
- Aberdeen University (1)
- Aberystwyth University Repository - Reino Unido (3)
- Academic Archive On-line (Karlstad 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 (7)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (2)
- Archive of European Integration (189)
- Aston University Research Archive (14)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (8)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (12)
- Biodiversity Heritage Library, United States (3)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (42)
- Boston University Digital Common (1)
- Brock University, Canada (4)
- Bucknell University Digital Commons - Pensilvania - USA (2)
- Bulgarian Digital Mathematics Library at IMI-BAS (21)
- CaltechTHESIS (5)
- Cambridge University Engineering Department Publications Database (63)
- CentAUR: Central Archive University of Reading - UK (38)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (39)
- Cochin University of Science & Technology (CUSAT), India (6)
- 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 (1)
- CUNY Academic Works (3)
- Deakin Research Online - Australia (24)
- Department of Computer Science E-Repository - King's College London, Strand, London (6)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Commons - Michigan Tech (2)
- Digital Commons at Florida International University (4)
- Digital Peer Publishing (1)
- DigitalCommons@The Texas Medical Center (6)
- DigitalCommons@University of Nebraska - Lincoln (1)
- Diposit Digital de la UB - Universidade de Barcelona (5)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (5)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (2)
- Greenwich Academic Literature Archive - UK (10)
- Helda - Digital Repository of University of Helsinki (9)
- Illinois Digital Environment for Access to Learning and Scholarship Repository (1)
- Indian Institute of Science - Bangalore - Índia (69)
- Instituto Gulbenkian de Ciência (1)
- Instituto Politécnico do Porto, Portugal (1)
- Lume - Repositório Digital da Universidade Federal do Rio Grande do Sul (1)
- Massachusetts Institute of Technology (6)
- Memorial University Research Repository (1)
- Ministerio de Cultura, Spain (2)
- National Center for Biotechnology Information - NCBI (21)
- Nottingham eTheses (1)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (1)
- Publishing Network for Geoscientific & Environmental Data (4)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (69)
- Queensland University of Technology - ePrints Archive (44)
- Repositorio Académico de la Universidad Nacional de Costa Rica (1)
- Repositório digital da Fundação Getúlio Vargas - FGV (4)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositorio Institucional de la Universidad de Málaga (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (40)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (1)
- School of Medicine, Washington University, United States (2)
- Universidad de Alicante (3)
- Universidad del Rosario, Colombia (3)
- Universidad Politécnica de Madrid (12)
- Universidade Complutense de Madrid (1)
- Universidade Federal do Pará (2)
- Universitat de Girona, Spain (3)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (4)
- Université de Montréal (3)
- Université de Montréal, Canada (12)
- University of Michigan (18)
- University of Queensland eSpace - Australia (15)
- WestminsterResearch - 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.