<p>The paper by Raghavendra is now also published and available <a href="http://drops.dagstuhl.de/opus/volltexte/2016/6206/pdf/LIPIcs-ICALP-2016-79.pdf" rel="nofollow noreferrer">here</a> under the title:</p>

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

<p>A related article has appeared in the Electronic Colloquium on Computational Complexity, Report No. 7 (2015), available <a href="https://arxiv.org/abs/1501.01598" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 3.0
2017-08-28T22:26:33.577Z
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.
CC BY-SA 3.0
2018-04-01T20:38:56.207Z
The link is down, please could you tell us the complexity of this algorithm?
juaninf
CC BY-SA 3.0
2018-04-03T11:53:36.420Z
The Links still should both work, please try again!
LeoW.
CC BY-SA 3.0
2017-08-28T17:46:34.220Z
2017-08-31T17:43:09.860Z
2017-08-31T17:43:09.860Z
LeoW.
<p>This is a paper that seems to improve upon the result. <a href="https://arxiv.org/pdf/1209.3995.pdf" rel="noreferrer">https://arxiv.org/pdf/1209.3995.pdf</a></p>

CC BY-SA 3.0
2016-11-06T22:00:12.747Z
2016-11-06T22:00:12.747Z
user43170
<p>In 2012, <a href="https://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations/" rel="noreferrer">Lipton wrote a blog entry</a> about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra.</p>

<p>The <a href="https://people.eecs.berkeley.edu/~prasad/linsystems.pdf" rel="noreferrer">link to Raghavendra's draft paper on the topic is now dead</a>, and I can't find anything on the subject on Raghavendra's website.</p>

<p>Is the result correct? Is a write-up available anywhere?</p>

<p>Thanks!</p>

<linear-algebra><finite-fields>
Status of Raghavendra's algorithm for solving linear systems in finite fields
okintheory
# Status of Raghavendra's algorithm for solving linear systems in finite fields

(Asked by: username_0 on 2016-11-06)

In 2012, [Lipton wrote a blog entry](https://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations/) 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](https://people.eecs.berkeley.edu/~prasad/linsystems.pdf), and I can't find anything on the subject on Raghavendra's website.

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

Thanks!

**Tags:** linear-algebra, finite-fields

---

## 2 answers

### Answer by username_1 on 2017-08-28. Score: 8 | Accepted answer

The paper by Raghavendra is now also published and available [here](http://drops.dagstuhl.de/opus/volltexte/2016/6206/pdf/LIPIcs-ICALP-2016-79.pdf) 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](https://arxiv.org/abs/1501.01598).

> **Comments:**
> **username_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)?  
> **username_3**: The link is down, please could you tell us the complexity of this algorithm?  
> **username_1**: The Links still should both work, please try again!  

---

### Answer by username_4 on 2016-11-06. Score: 11

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


---

