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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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.
    Commented Aug 28, 2017 at 22:26
  • $\begingroup$ The link is down, please could you tell us the complexity of this algorithm? $\endgroup$
    – juaninf
    Commented Apr 1, 2018 at 20:38
  • $\begingroup$ The Links still should both work, please try again! $\endgroup$
    – LeoW.
    Commented Apr 3, 2018 at 11:53
11
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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