15
$\begingroup$

In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra.

The link to Raghavendra's draft paper on the topic is now dead, and I can't find anything on the subject on Raghavendra's website.

Is the result correct? Is a write-up available anywhere?

Thanks!

$\endgroup$
8
$\begingroup$

The paper by Raghavendra is now also published and available here under the title:

Correlation Decay and Tractability of CSPs, appeared in the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).

A related article has appeared in the Electronic Colloquium on Computational Complexity, Report No. 7 (2015), available here.

$\endgroup$
  • 2
    $\begingroup$ Can you give details that will enable us to find the paper in the future if this link stops working? Maybe paper title, authors, and where published (if anywhere)? $\endgroup$ – D.W. Aug 28 '17 at 22:26
  • $\begingroup$ The link is down, please could you tell us the complexity of this algorithm? $\endgroup$ – juaninf Apr 1 '18 at 20:38
  • $\begingroup$ The Links still should both work, please try again! $\endgroup$ – LeoW. Apr 3 '18 at 11:53
11
$\begingroup$

This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.