Recentemente, houve novos resultados em estudos experimentais baseados em computador do Problema da Discrepância de Erdos (EDP) (via solucionadores SAT, citados abaixo). Esse problema foi citado e estudado por vários pesquisadores (T) de CS. No entanto, os links (possivelmente profundos?) Para (T) CS não são tão óbvios.
Quais são os links do EDP para (T) CS?
Seguem algumas referências que demonstram interesse da comunidade (T) CS na EDP:
Ataque SAT à EDP por Konev e Lisitsa e reação por Gowers ; além disso, outras conexões com o TCS empírico / experimental (por exemplo, provas de teoremas automatizados SAT)
Introdução ao EDP e técnicas no blog de Lipton
EDP e Privacidade Diferencial no blog Windows on Theory, de Talwar
Projeto de polímata da EDP , com algumas contribuições de cientistas da computação
Respostas:
Existem muitos elos entre a teoria da discrepância e a ciência da computação, e Bernard Chazelle examinou lindamente alguns deles em seu livro . Também foram encontrados vários links mais recentemente, por exemplo, o post de Kunal no blog fala sobre a conexão com a privacidade diferencial de [MN] e [NTZ] . Outro exemplo é a ideia de Larsen de usar discrepâncias para provar limites inferiores do tempo de atualização / consulta para estruturas de dados dinâmicas. Muitos desses links podem ser instanciados com progressões aritméticas homogêneas (HAPs). Isso daria:
No entanto, há duas coisas que você deve realizar com relação a esses links. Uma é que não está claro que os espaços de intervalo dos HAPs sejam muito naturais. Quando você espera ter uma entrada com um conjunto múltiplo de números inteiros e deseja responder quantos elementos de um HAP estão na entrada? Não consigo pensar em uma situação quando isso acontece, mas talvez esteja perdendo alguma coisa.
Outra coisa que você deve perceber é que todos esses aplicativos dependem da noção de discrepância hereditária . Essa noção é mais robusta que a discrepância, o que a torna mais tratável: existem limites inferiores mais fortes disponíveis, é aproximada de fatores polilogarítmicos e é aproximadamente igual ao valor de um problema de otimização convexa. O resultado sobre o qual Kunal fala na postagem do blog (o artigo está aqui ) e a construção de Alon e Kalai sobre a qual Kalai escreveu nesta postagem do blogjuntos resolvem essencialmente a discrepância hereditária dos HAPs. Como explica Kunal, a intuição para o limite inferior da discrepância hereditária dos HAPs veio da estreita conexão entre discrepância hereditária e privacidade diferencial, juntamente com resultados anteriores em privacidade diferencial.
No entanto, a EDP trata da discrepância de HAPs. A discrepância é muito mais frágil do que a discrepância hereditária, e isso dificulta o limite inferior. Isso também o torna menos útil em aplicativos que a discrepância hereditária. E é por isso que a EDP ainda está aberta, enquanto a questão da discrepância hereditária é bastante bem compreendida.
Deixe-me terminar com uma abordagem para atacar a EDP, inspirada nas idéias da ciência da computação. Existe uma maneira de diminuir a discrepância de um programa semidefinido; consulte a pesquisa da Bansal para obter detalhes. O valor ideal do programa semidefinido é limitado pelo valor de qualquer solução viável para seu programa duplo. Assim, pode-se tentar provar a EDP exibindo uma família de soluções duplas para esse relaxamento semidefinido de discrepância e mostrando que o valor das soluções duplas vai para o infinito. Não vejo razão para que tal ataque não funcione, em particular não sabemos como construir soluções para o relaxamento semidefinido que têm valor constante para instâncias arbitrariamente grandes. De fato, grande parte do esforço no polímato5 foi centrado em encontrar ou descartar soluções duplas com estrutura específica.
fonte