15

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!

okintheory
  • 253
  • 1
  • 4

2 Answers2

11

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

user43170
  • 163
  • 7
8

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.

LeoW.
  • 118
  • 1
  • 9
  • 2
    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)? – D.W. Aug 28 '17 at 22:26
  • The link is down, please could you tell us the complexity of this algorithm? – juaninf Apr 01 '18 at 20:38
  • The Links still should both work, please try again! – LeoW. Apr 03 '18 at 11:53