Minha pergunta diz respeito à prova do principal teorema de Ajtai em seu artigo inovador de 1996, Gerando instâncias rígidas de problemas de treliça , o que indica uma conexão entre os problemas de treliça de pior caso e de malha dura de caso médio. Esta prova é difícil para mim entender. Existe uma exposição clara dessa prova na literatura?
integer-lattice
Krishnan Narayanan
fonte
fonte
Respostas:
Você pode tentar ler artigos mais recentes, como Reduções de pior caso a caso médio com base nas medidas gaussianas de Miccancio e Regev ou notas de aula de Regev sobre o assunto (você pode ler o curso inteiro ).
fonte