Um Limite Inferior Quase Quadrático para Otimização Linear sobre Corpos Convexos no Modelo de Oráculo de Pertencimento

Demonstramos limites inferiores quase quadráticos para algoritmos aleatórios de otimização linear e amostragem uniforme sobre corpos convexos no modelo de oráculo de pertencimento. Para otimização linear, isso corresponde ao limite superior quase quadrático conhecido, até um fator poli‑logarítmico na dimensão. Para amostragem uniforme, isso melhora o limite inferior linear anterior. Nossa construção também implica o mesmo limite inferior para estimativa de volume.