Theory Group

Complexity Theory Meet (Co-tMeet)

This is an informal reading group organized by the complexity theory group. All announcements about the meetings will be sent to the mailing list. The participants also collectively maintain a list of papers that they wish to see presented (at some point). Any participant can contribute to this list or volunteer for presenting one of the listed papers. Click here for volunteering to present a paper or adding a paper of your choice to this wish list.

Next Talk

• Meeting 28 : Wed, Jul 03, 2019, 03:30 pm - 05:00 pm (Speaker : Ankit Kumar Yadav)

On the Space Complexity of Parameterized Problems

Ref:
Exercises
Reading

On the Space Complexity of Parameterized Problems


Ref:

None

• Meeting 27 : Wed, Jun 26, 2019, 03:30 pm - 05:00 pm (Speaker : Swaroop N P)

In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω(√ d), and were obtained from arguments based on Wronskian determinants and "shifted derivatives." We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as "lacunary polynomial interpolation")

Ref:	Lower Bounds by Birkhoff Interpolation
Exercises
Reading

In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω(√ d), and were obtained from arguments based on Wronskian determinants and "shifted derivatives." We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as "lacunary polynomial interpolation")


Ref:	Lower Bounds by Birkhoff Interpolation

Upcoming Talks

• Meeting 26 : Wed, Apr 10, 2019, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)

<a href="https://arxiv.org/abs/1611.05558">Probabilistic Rank and Matrix Rigidity</a> - Josh Alman, Ryan Williams

Ref:
Exercises
Reading

Probabilistic Rank and Matrix Rigidity - Josh Alman, Ryan Williams


Ref:

None

Past Talks (click here)

• Meeting 25 : Wed, Apr 03, 2019, 03:30 pm - 05:00 pm (Speaker : Sagar Bisoyi)

<a href="https://arxiv.org/abs/1504.01431">If the Current Clique Algorithms are Optimal, so is Valiant’s Parser</a>. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams.

Ref:
Exercises
Reading

If the Current Clique Algorithms are Optimal, so is Valiant’s Parser. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams.


Ref:

None

• Meeting 24 : Wed, Feb 20, 2019, 03:30 pm - 04:45 pm (Speaker : Swaroop N P)

<a href="https://arxiv.org/pdf/1503.07705.pdf">Log-concavity and lower bounds for arithmetic circuits</a>.

Ref:	<a href="https://arxiv.org/pdf/1503.07705.pdf">https://arxiv.org/pdf/1503.07705.pdf</a>
Exercises
Reading

Log-concavity and lower bounds for arithmetic circuits.


Ref:	https://arxiv.org/pdf/1503.07705.pdf

• Meeting 23 : Wed, Aug 15, 2018, 03:30 pm - 05:00 pm (Speaker : Purnata Ghosal)

<a href="https://eccc.weizmann.ac.il/report/2018/124/">Separating Monotone VP and VNP</a>

Ref:
Exercises
Reading

Separating Monotone VP and VNP


Ref:

None

• Meeting 22 : Tue, Jul 24, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)

Introduction to Lie Algebra - II

Ref:
Exercises
Reading

Introduction to Lie Algebra - II


Ref:

None

• Meeting 21 : Wed, Jul 18, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)

<a href="http://www.cs.colorado.edu/~jgrochow/grochow-thesis.pdf">An introduction to Lie Algebra</a>.

Ref:
Exercises
Reading

An introduction to Lie Algebra.


Ref:

None

• Meeting 20 : Wed, Jun 27, 2018, 10:00 am - 11:30 am (Speaker : Yadu Vasudev)

<a href="https://eccc.weizmann.ac.il/report/2018/050/">Every set in P is strongly testable under a suitable encoding</a> - Irit Dinur, Oded Goldreich, Tom Gur

Ref:
Exercises
Reading

Every set in P is strongly testable under a suitable encoding - Irit Dinur, Oded Goldreich, Tom Gur


Ref:

None

• Meeting 19 : Tue, Jun 19, 2018, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)

<a href="https://eccc.weizmann.ac.il/report/2017/129/revision/3/download/">An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with 4 Rounds</a> - Or Meir.

Ref:
Exercises
Reading

An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with 4 Rounds - Or Meir.


Ref:

None

• Meeting 18 : Mon, Jun 11, 2018, 10:00 am - 11:30 am (Speaker : Jayalal Sarma)

Karchmer-Wigderson Games, Universal Relations. Upper and Lower Bounds.

Ref:
Exercises
Reading

Karchmer-Wigderson Games, Universal Relations. Upper and Lower Bounds.


Ref:

None

• Meeting 17 : Wed, Mar 30, 2016, 04:15 pm - 06:00 am (Speaker : Sajin)

Addition is exponentially harder than counting for shallow monotone circuits

Ref:	http://www.eccc.hpi-web.de/report/2015/123/download/
Exercises
Reading

Addition is exponentially harder than counting for shallow monotone circuits


Ref:	http://www.eccc.hpi-web.de/report/2015/123/download/

• Meeting 16 : Tue, Mar 15, 2016, 04:15 pm - 05:30 pm (Speaker : Purnata Ghosal)

<a href="http://www.wisdom.weizmann.ac.il/~oded/p_aq.html">On Derandomizing Algorithms that Err Extremely Rarely</a> - Oded Goldreich and Avi Wigderson

Ref:
Exercises
Reading

On Derandomizing Algorithms that Err Extremely Rarely - Oded Goldreich and Avi Wigderson


Ref:

None

• Meeting 15 : Wed, Oct 07, 2015, 04:00 pm - 05:30 pm (Speaker : Meenakshi Ray)

<a href="http://arxiv.org/abs/1312.6680">Faster all-pairs shortest paths via circuit complexity</a> - Ryan Williams.

Ref:
Exercises
Reading

Faster all-pairs shortest paths via circuit complexity - Ryan Williams.


Ref:

None

• Meeting 14 : Wed, Sep 23, 2015, 04:00 pm - 07:30 pm (Speaker : Sunil)

<a href="http://arxiv.org/abs/1503.05879"> Regular realizability problems</a>.

Ref:	<a href="http://arxiv.org/abs/1503.05879">Regular realizability problems and regular languages </a> by Alexander Rubstov.
Exercises
Reading

Regular realizability problems.


Ref:	Regular realizability problems and regular languages by Alexander Rubstov.

• Meeting 13 : Wed, Sep 02, 2015, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)

(Part 2/2) <a href="http://eccc.hpi-web.de/report/2014/169/">Lower bounds for monotone counting circuits</a> - Stasys Jukna.

Ref:
Exercises
Reading

(Part 2/2) Lower bounds for monotone counting circuits - Stasys Jukna.


Ref:

None

• Meeting 12 : Mon, Aug 24, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)

(Part 1/2) <a href="http://eccc.hpi-web.de/report/2014/169/">Lower bounds for monotone counting circuits</a> - Stasys Jukna

Ref:
Exercises
Reading

(Part 1/2) Lower bounds for monotone counting circuits - Stasys Jukna


Ref:

None

• Meeting 11 : Wed, Aug 12, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)

<a href="http://arxiv.org/abs/1205.1478"> A Tail Bound for Read-k Families of Functions</a> - Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan.

Ref:
Exercises
Reading	<a href="http://www.eccc.hpi-web.de/report/2014/019/download"> Inequalities and tail bounds for elementary symmetric polynomials.</a> Parikshit Gopalan and AMir Yehudayoff ECCC, TR14-19.

A Tail Bound for Read-k Families of Functions - Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan.


Ref:	None
Reading:	Inequalities and tail bounds for elementary symmetric polynomials. Parikshit Gopalan and AMir Yehudayoff ECCC, TR14-19.

• Meeting 10 : Wed, Jul 01, 2015, 04:00 pm - 05:30 pm (Speaker : Dinesh K)

<a href="http://eccc.hpi-web.de/report/2014/173/">Majority is incompressible by AC0[p] circuits</a> - Igor Carboni Oliveira, Rahul Santhanam

Ref:
Exercises
Reading

Majority is incompressible by AC0[p] circuits - Igor Carboni Oliveira, Rahul Santhanam


Ref:

None

• Meeting 09 : Wed, Jun 17, 2015, 04:00 pm - 05:30 pm (Speaker : Ramya C.)

<a href="http://eccc.hpi-web.de/report/2015/016/">An O(n^epsilon) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs</a> - Diptarka Chakraborty, Raghunath Tewari

Ref:
Exercises
Reading

An O(n^epsilon) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs - Diptarka Chakraborty, Raghunath Tewari


Ref:

None

• Meeting 08 : Wed, May 13, 2015, 04:00 pm - 05:30 pm (Speaker : Krishnamoorthy Dinesh)

<a href="http://eccc.hpi-web.de/report/2014/048/">Shrinkage Exponent of Boolean Formulas from Quantum Query Complexity</a> - Avishay Tal

Ref:
Exercises
Reading

Shrinkage Exponent of Boolean Formulas from Quantum Query Complexity - Avishay Tal


Ref:

None

• Meeting 07 : Wed, May 06, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)

Part (2/2) of <a href="arxiv.org/abs/1410.8420">Learning circuits with few negations</a> - Blais, Canonne, Oliveira, Servedio, Tan

Ref:
Exercises
Reading

Part (2/2) of Learning circuits with few negations - Blais, Canonne, Oliveira, Servedio, Tan


Ref:

None

• Meeting 06 : Wed, Apr 29, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)

Part (1/2) of <a href="arxiv.org/abs/1410.8420">Learning circuits with few negations</a> - Blais, Canonne, Oliveira, Servedio, Tan

Ref:
Exercises
Reading

Part (1/2) of Learning circuits with few negations - Blais, Canonne, Oliveira, Servedio, Tan


Ref:

None

• Meeting 05 : Wed, Apr 22, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)

Part (3/3) of <a href="http://eccc.hpi-web.de/report/2015/012/">Lower Bounds for Clique vs. Independent Set</a> - Mika Goos

Ref:
Exercises
Reading

Part (3/3) of Lower Bounds for Clique vs. Independent Set - Mika Goos


Ref:

None

• Meeting 04 : Tue, Apr 07, 2015, 04:00 pm - 05:15 pm (Speaker : Jayalal Sarma)

Part (2/3) <a href="http://eccc.hpi-web.de/report/2015/012/">Lower Bounds for Clique vs. Independent Set</a> - Mika Goos

Ref:
Exercises
Reading

Part (2/3) Lower Bounds for Clique vs. Independent Set - Mika Goos


Ref:

None

• Meeting 03 : Wed, Apr 01, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)

Part (1/3) <a href="http://eccc.hpi-web.de/report/2015/012/">Lower Bounds for Clique vs. Independent Set</a> - Mika Goos

Ref:
Exercises
Reading

Part (1/3) Lower Bounds for Clique vs. Independent Set - Mika Goos


Ref:

None

• Meeting 02 : Wed, Mar 25, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)

(Part II) <a href="http://arxiv.org/abs/1302.4536">An o(n) monotonicity tester for Boolean functions over the hypercube</a> - Deeparnab Chakrabarty, C. Seshadhri

Ref:
Exercises
Reading

(Part II) An o(n) monotonicity tester for Boolean functions over the hypercube - Deeparnab Chakrabarty, C. Seshadhri


Ref:

None

• Meeting 01 : Wed, Mar 18, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)

(Part I) <a href="http://arxiv.org/abs/1302.4536">An o(n) monotonicity tester for Boolean functions over the hypercube</a> - Deeparnab Chakrabarty, C. Seshadhri

Ref:
Exercises
Reading	Recommended articles for further reading: <br> <ul> <li> <a href="http://eccc.hpi-web.de/report/2015/011/"> On Monotonicity Testing and Boolean Isoperimetric type Theorems. </a> By Subhash Khot, Dor Minzer, Muli Safra. </li> <li><a href="http://arxiv.org/abs/1412.5657">Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries.</a> Xi Chen, Anindya De, Rocco A. Servedio and Li-Yang Tan </li> </ul>

(Part I) An o(n) monotonicity tester for Boolean functions over the hypercube - Deeparnab Chakrabarty, C. Seshadhri


Ref:	None
Reading:	Recommended articles for further reading: On Monotonicity Testing and Boolean Isoperimetric type Theorems. By Subhash Khot, Dor Minzer, Muli Safra. Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries. Xi Chen, Anindya De, Rocco A. Servedio and Li-Yang Tan