Technion - Israel Institute of Technology
		238900 - Seminar on open problems in computational complexity
		Spring 2012
	Literature Rigidity Deterministic approximation algorithms for the nearest codeword problem Author:   Noga Alon, Rina Panigrahy and Sergey Yekhanin Link:   http://research.microsoft.com/en-us/um/people/yekhanin/Papers/NCP_approx.pdf Circuit Lower Bounds, Help Functions, and the Remote Point Problem Author:   Vikraman Arvind and Srikanth Srinivasan Link:   http://arxiv.org/pdf/0911.4337v1.pdf More on Average Case vs Approximation Complexity Author:   Michael Alekhnovich Link:   http://www.math.ias.edu/~misha/papers/average.ps Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity Author:   Satyanarayana V. Lokam Link:   http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.4411 Lower Bounds for Arithmetic Circuits Non-commutative circuits and the sum-of-squares problem Author:   Pavel Hrubes, Amir Yehudayoff and Avi Wigderson Link:   http://eccc.hpi-web.de/report/2010/021/download Elusive Functions and Lower Bounds for Arithmetic Circuits Author:   Ran Raz Link:   http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pelusive.new.pdf Lower Bounds on Arithmetic Circuits via Partial Derivatives Author:   Noan Nisan and Avi Wigderson Link:   http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf On the Complexity of Matrix Product' Author:   Ran Raz Link:   http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatrix.ps Locally Correctable Codes Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes Author:   Boaz Barak, Zeev Dvir, Amir Yehudayoff and Avi Wigderson Link:   http://www.cs.princeton.edu/~zdvir/papers/BDWY11.pdf Tight lower bounds for 2-query LCCs over finite fields Author:   Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf and Amir Shpilka Link:   http://eccc.hpi-web.de/report/2011/054/download On the efficiency of local decoding procedures for error-correcting codes. Author:   Jonathan Katz and Luca Trevisan Link:   http://www.cs.berkeley.edu/~luca/pubs/stoc00kt.ps Graph Isomorphism Faster Isomorphism Testing of Strongly Regular Graphs Author:   Dan Spielman Link:   http://cs-www.cs.yale.edu/homes/spielman/Research/grisom.html An optimal lower bound on the number of variables for graph identifications Author:   Jin-yi Cai, Martin Fürer and Neil Immerman: Link:   http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4863 Isomorphism of graphs of bounded valence can be tested in polynomial time Author:   Eugene M. Luks Link:   http://ix.cs.uoregon.edu/~luks/iso.pdf 3-Coloring New Approximation Algorithms for Graph Coloring Author:   Avrim Blum Link:   http://www.cse.iitk.ac.in/users/niteshj/blum_90_new_approx.ps Approximate graph coloring by semidefinite programming Author:   David Karger, Rajeev Motwani and Madhu Sudan Link:   http://people.csail.mit.edu/madhu/papers/1994/kms-journ.pdf On the hardness of 4-coloring a 3-colorable graph Author:   Venkatesan Guruswami and Sanjeev Khanna Link:   http://www.cs.cmu.edu/~venkatg/pubs/papers/3coloring.ps Communication Complexity On Rank vs. Communication Complexity Author:   Noam Nisan and Avi Wigderson Link:   http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/RANK/journal.pdf Complexity Measures and Decision Tree Complexity: A Survey Author:   Harry Buhrman and Ronald de Wolf. Link:   http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Towards deterministic tree code constructions Author:   Mark Braverman Link:   http://eccc.hpi-web.de/report/2011/064/download The multiparty communication complexity of set disjointness Author:   Alexander Sherstov Link:   http://eccc.hpi-web.de/report/2011/145/download Computations over Composites On ACC Author:   Richard Beigel and Jun Tarui Link:   http://knight.cis.temple.edu/~beigel/papers/bt-acc-cc.html Non-Uniform ACC Circuit Lower Bounds Author:   Ryan Williams Link:   http://www.stanford.edu/~rrwill/acc-lbs.pdf A lower bound on the mod 6 degree of the OR function Author:   Gabor Tardos and David Mix Barrington Link:   http://www.renyi.hu/~tardos/david.ps Linear Systems over Composite Moduli Author:   Arkadev Chattopadhyay and Avi Wigderson Link:   http://www.cs.toronto.edu/~arkadev/singleLayer2G.pdf Analysis of Boolean functions Boolean functions with small spectral norm Author:   Ben Green and Tom Sanders Link:   http://www.arxiv.org/pdf/math.CA/0605524 An O(n^log log n) learning algorithm for DNF under the uniform distribution Author:   Yishay Mansour Link:   http://dl.acm.org/citation.cfm?id=130391 Notes:   Paper can be downloaded from a Technion computer