Status do algoritmo de Raghavendra para resolver sistemas lineares em campos finitos

15

Em 2012, Lipton escreveu uma entrada no blog sobre um novo algoritmo para resolver sistemas lineares em campos finitos por Prasad Raghavendra.

O link para o rascunho do artigo de Raghavendra sobre o assunto agora está morto , e não consigo encontrar nada sobre o assunto no site de Raghavendra.

O resultado está correto? Existe um artigo disponível em algum lugar?

Obrigado!

linear-algebra finite-fields okintheory
fonte

8

O artigo de Raghavendra agora também está publicado e disponível aqui sob o título:

O Decaimento de Correlação e a Rastrabilidade dos CSPs , apareceu no 43º Colóquio Internacional sobre Autômatos, Idiomas e Programação (ICALP 2016).

Um artigo relacionado foi publicado no Colóquio Eletrônico sobre Complexidade Computacional, Relatório No. 7 (2015), disponível aqui .

LeoW.
fonte

2

Você pode fornecer detalhes que nos permitirão encontrar o documento no futuro se esse link parar de funcionar? Talvez título do artigo, autores e onde publicado (se houver)?

DW

O link está inoperante. Você poderia nos dizer a complexidade desse algoritmo?

Juaninf #

Os links ainda devem funcionar, tente novamente!

LeoW.

11

Este é um artigo que parece melhorar o resultado. https://arxiv.org/pdf/1209.3995.pdf

user43170
fonte

Status do algoritmo de Raghavendra para resolver sistemas lineares em campos finitos

Respostas: