Search dblp for Publications

export results for "toc:db/conf/coco/coco2016.bht:"

 download as .bib file

@inproceedings{DBLP:conf/coco/0001S16,
  author    = {Mrinal Kumar and
               Shubhangi Saraf},
  title     = {Arithmetic Circuits with Locally Low Algebraic Rank},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {34:1--34:27},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/0001S16a,
  author    = {Mrinal Kumar and
               Shubhangi Saraf},
  title     = {Sums of Products of Polynomials in Few Variables: Lower Bounds and
               Polynomial Identity Testing},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {35:1--35:29},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/AaronsonAIKS16,
  author    = {Scott Aaronson and
               Andris Ambainis and
               Janis Iraids and
               Martins Kokainis and
               Juris Smotrovs},
  title     = {Polynomials, Quantum Query Complexity, and Grothendieck's Inequality},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {25:1--25:19},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/AaronsonB16,
  author    = {Scott Aaronson and
               Shalev Ben{-}David},
  title     = {Sculpting Quantum Speedups},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {26:1--26:28},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/AiHLW16,
  author    = {Yuqing Ai and
               Wei Hu and
               Yi Li and
               David P. Woodruff},
  title     = {New Characterizations in Turnstile Streams with Applications},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {20:1--20:22},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/AmbainisKK16,
  author    = {Andris Ambainis and
               Martins Kokainis and
               Robin Kothari},
  title     = {Nearly Optimal Separations Between Communication (or Query) Complexity
               and Partitions},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {4:1--4:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/AndersonFSSV16,
  author    = {Matthew Anderson and
               Michael A. Forbes and
               Ramprasad Saptharishi and
               Amir Shpilka and
               Ben Lee Volk},
  title     = {Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching
               Programs},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {30:1--30:25},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ArtemenkoIKS16,
  author    = {Sergei Artemenko and
               Russell Impagliazzo and
               Valentine Kabanets and
               Ronen Shaltiel},
  title     = {Pseudorandomness When the Odds are Against You},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {9:1--9:35},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/BeaudrapG16,
  author    = {J. Niel de Beaudrap and
               Sevag Gharibian},
  title     = {A Linear Time Algorithm for Quantum 2-SAT},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {27:1--27:21},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/BhattacharyyaG16,
  author    = {Arnab Bhattacharyya and
               Sivakanth Gopi},
  title     = {Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {12:1--12:17},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/BoulandMZ16,
  author    = {Adam Bouland and
               Laura Mancinska and
               Xue Zhang},
  title     = {Complexity Classification of Two-Qubit Commuting Hamiltonians},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {28:1--28:33},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/BrakensiekG16,
  author    = {Joshua Brakensiek and
               Venkatesan Guruswami},
  title     = {New Hardness Results for Graph and Hypergraph Colorings},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {14:1--14:27},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/CarmosinoIKK16,
  author    = {Marco L. Carmosino and
               Russell Impagliazzo and
               Valentine Kabanets and
               Antonina Kolokolova},
  title     = {Learning Algorithms from Natural Proofs},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {10:1--10:24},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ChattopadhyayZ16,
  author    = {Eshan Chattopadhyay and
               David Zuckerman},
  title     = {New Extractors for Interleaved Sources},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {7:1--7:28},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ChenSS16,
  author    = {Ruiwen Chen and
               Rahul Santhanam and
               Srikanth Srinivasan},
  title     = {Average-Case Lower Bounds and Satisfiability Algorithms for Small
               Threshold Circuits},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {1:1--1:35},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/Cohen16,
  author    = {Gil Cohen},
  title     = {Non-Malleable Extractors - New Tools and Improved Constructions},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {8:1--8:29},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/DengEFLQX16,
  author    = {Xiaotie Deng and
               Jack R. Edmonds and
               Zhe Feng and
               Zhengyang Liu and
               Qi Qi and
               Zeying Xu},
  title     = {Understanding PPA-Completeness},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {23:1--23:25},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/DinurM16,
  author    = {Irit Dinur and
               Or Meir},
  title     = {Toward the {KRW} Composition Conjecture: Cubic Formula Lower Bounds
               via Communication Complexity},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {3:1--3:51},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/FilmusKMW16,
  author    = {Yuval Filmus and
               Guy Kindler and
               Elchanan Mossel and
               Karl Wimmer},
  title     = {Invariance Principle on the Slice},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {15:1--15:10},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/FilmusM16,
  author    = {Yuval Filmus and
               Elchanan Mossel},
  title     = {Harmonicity and Invariance on Slices of the Boolean Cube},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {16:1--16:13},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ForbesKS16,
  author    = {Michael A. Forbes and
               Mrinal Kumar and
               Ramprasad Saptharishi},
  title     = {Functional Lower Bounds for Arithmetic Circuits and Connections to
               Boolean Circuit Complexity},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {33:1--33:19},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ForbesSTW16,
  author    = {Michael A. Forbes and
               Amir Shpilka and
               Iddo Tzameret and
               Avi Wigderson},
  title     = {Proof Complexity Lower Bounds from Algebraic Circuit Complexity},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {32:1--32:17},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/FortnowS16,
  author    = {Lance Fortnow and
               Rahul Santhanam},
  title     = {New Non-Uniform Lower Bounds for Uniform Classes},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {19:1--19:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/GoosJ16,
  author    = {Mika G{\"{o}}{\"{o}}s and
               T. S. Jayram},
  title     = {A Composition Theorem for Conical Juntas},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {5:1--5:16},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/GopalanSW16,
  author    = {Parikshit Gopalan and
               Rocco A. Servedio and
               Avi Wigderson},
  title     = {Degree and Sensitivity: Tails of Two Distributions},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {13:1--13:23},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/GurjarKS16,
  author    = {Rohit Gurjar and
               Arpita Korwar and
               Nitin Saxena},
  title     = {Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious
               ABPs},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {29:1--29:16},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/GuruswamiR16,
  author    = {Venkatesan Guruswami and
               Jaikumar Radhakrishnan},
  title     = {Tight Bounds for Communication-Assisted Agreement Distillation},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {6:1--6:17},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/HarrowNW16,
  author    = {Aram Wettroth Harrow and
               Anand Natarajan and
               Xiaodi Wu},
  title     = {Tight SoS-Degree Bounds for Approximate Nash Equilibria},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {22:1--22:25},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/HiraharaW16,
  author    = {Shuichi Hirahara and
               Osamu Watanabe},
  title     = {Limits of Minimum Circuit Size Problem as Oracle},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {18:1--18:20},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/KimK16,
  author    = {John Y. Kim and
               Swastik Kopparty},
  title     = {Decoding Reed-Muller Codes Over Product Sets},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {11:1--11:28},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/LeePWY16,
  author    = {Troy Lee and
               Anupam Prakash and
               Ronald de Wolf and
               Henry Yuen},
  title     = {On the Sum-of-Squares Degree of Symmetric Quadratic Functions},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {17:1--17:31},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/ODonnellZ16,
  author    = {Ryan O'Donnell and
               Yu Zhao},
  title     = {Polynomial Bounds for Decoupling, with Applications},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {24:1--24:18},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/Sinha16,
  author    = {Gaurav Sinha},
  title     = {Reconstruction of Real Depth-3 Circuits with Top Fan-In 2},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {31:1--31:53},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/Vishnoi16,
  author    = {Nisheeth K. Vishnoi},
  title     = {Evolution and Computation (Invited Talk)},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {21:1--21:1},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/Williams16,
  author    = {Richard Ryan Williams},
  title     = {Strong {ETH} Breaks With Merlin and Arthur: Short Non-Interactive
               Proofs of Batch Evaluation},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {2:1--2:17},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@inproceedings{DBLP:conf/coco/X16,
  title     = {Front Matter, Table of Contents, Preface, Awards, Conference Organization,
               External Reviewers},
  booktitle = {Conference on Computational Complexity},
  series    = {LIPIcs},
  volume    = {50},
  pages     = {0:i--0:xvi},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
@proceedings{DBLP:conf/coco/2016,
  editor    = {Ran Raz},
  title     = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to
               June 1, 2016, Tokyo, Japan},
  series    = {LIPIcs},
  volume    = {50},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016}
}
a service of Schloss Dagstuhl - Leibniz Center for Informatics