×

31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. (English) Zbl 1351.68027

LIPIcs – Leibniz International Proceedings in Informatics 50. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). ix, 35 articles, not consecutively paged, electronic only, open access (2016).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1329.68038].
Indexed articles:
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth, Average-case lower bounds and satisfiability algorithms for small threshold circuits, Article 1, 35 p. [Zbl 1380.68191]
Williams, Richard Ryan, Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation, Article 2, 17 p. [Zbl 1380.68234]
Dinur, Irit; Meir, Or, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, Article 3, 51 p. [Zbl 1380.68193]
Ambainis, Andris; Kokainis, Martins; Kothari, Robin, Nearly optimal separations between communication (or query) complexity and partitions, Article 4, 14 p. [Zbl 1380.68209]
Göös, Mika; Jayram, T. S., A composition theorem for conical juntas, Article 5, 16 p. [Zbl 1380.68198]
Guruswami, Venkatesan; Radhakrishnan, Jaikumar, Tight bounds for communication-assisted agreement distillation, Article 6, 17 p. [Zbl 1380.94067]
Chattopadhyay, Eshan; Zuckerman, David, New extractors for interleaved sources, Article 7, 28 p. [Zbl 1380.68183]
Cohen, Gil, Non-malleable extractors – new tools and improved constructions, Article 8, 29 p. [Zbl 1380.68172]
Artemenko, Sergei; Impagliazzo, Russell; Kabanets, Valentine; Shaltiel, Ronen, Pseudorandomness when the odds are against you, Article 9, 35 p. [Zbl 1380.68434]
Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina, Learning algorithms from natural proofs, Article 10, 24 p. [Zbl 1380.68242]
Kim, John Y.; Kopparty, Swastik, Decoding Reed-Muller codes over product sets, Article 11, 28 p. [Zbl 1380.94148]
Bhattacharyya, Arnab; Gopi, Sivakanth, Lower bounds for constant query affine-invariant LCCs and LTCs, Article 12, 27 p. [Zbl 1380.94143]
Gopalan, Parikshit; Servedio, Rocco A.; Wigderson, Avi, Degree and sensitivity: tails of two distributions, Article 13, 23 p. [Zbl 1380.68223]
Brakensiek, Joshua; Guruswami, Venkatesan, New hardness results for graph and hypergraph colorings, Article 14, 27 p. [Zbl 1380.68190]
Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl, Invariance principle on the slice, Article 15, 10 p. [Zbl 1380.60020]
Filmus, Yuval; Mossel, Elchanan, Harmonicity and invariance on slices of the Boolean cube, Article 16, 13 p. [Zbl 1380.60021]
Lee, Troy; Prakash, Anupam; de Wolf, Ronald; Yuen, Henry, On the sum-of-squares degree of symmetric quadratic functions, Article 17, 31 p. [Zbl 1380.68203]
Hirahara, Shuichi; Watanabe, Osamu, Limits of minimum circuit size problem as oracle, Article 18, 20 p. [Zbl 1380.68240]
Fortnow, Lance; Santhanam, Rahul, New non-uniform lower bounds for uniform classes, Article 19, 14 p. [Zbl 1380.68196]
Ai, Yuqing; Hu, Wei; Li, Yi; Woodruff, David P., New characterizations in turnstile streams with applications, Article 20, 22 p. [Zbl 1380.68208]
Harrow, Aram; Natarajan, Anand V.; Wu, Xiaodi, Tight SoS-degree bounds for approximate Nash equilibria, Article 22, 25 p. [Zbl 1380.91015]
Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying, Understanding PPA-completeness, Article 23, 25 p. [Zbl 1380.68192]
O’Donnell, Ryan; Zhao, Yu, Polynomial bounds for decoupling, with applications, Article 24, 18 p. [Zbl 1380.68231]
Aaronson, Scott; Ambainis, Andris; Iraids, Janis; Kokainis, Martins; Smotrovs, Juris, Polynomials, quantum query complexity, and Grothendieck’s inequality, Article 25, 19 p. [Zbl 1380.68184]
Aaronson, Scott; Ben-David, Shalev, Sculpting quantum speedups, Article 26, 28 p. [Zbl 1380.68185]
de Beaudrap, Niel; Gharibian, Sevag, A linear time algorithm for quantum 2-SAT, Article 27, 21 p. [Zbl 1380.68237]
Bouland, Adam; Mancinska, Laura; Zhang, Xue, Complexity classification of two-qubit commuting Hamiltonians, Article 28, 33 p. [Zbl 1380.81084]
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin, Identity testing for constant-width, and commutative, read-once oblivious ABPs, Article 29, 16 p. [Zbl 1380.68224]
Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee, Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs, Article 30, 25 p. [Zbl 1380.68175]
Sinha, Gaurav, Reconstruction of real depth-3 circuits with top fan-in 2, Article 31, 53 p. [Zbl 1380.68438]
Forbes, Michael A.; Shpilka, Amir; Tzameret, Iddo; Wigderson, Avi, Proof complexity lower bounds from algebraic circuit complexity, Article 32, 17 p. [Zbl 1380.68195]
Forbes, Michael A.; Kumar, Mrinal; Saptharishi, Ramprasad, Functional lower bounds for arithmetic circuits and connections to Boolean circuit complexity, Article 33, 19 p. [Zbl 1380.68194]
Kumar, Mrinal; Saraf, Shubhangi, Arithmetic circuits with locally low algebraic rank, Article 34, 27 p. [Zbl 1380.68200]
Kumar, Mrinal; Saraf, Shubhangi, Sums of products of polynomials in few variables: lower bounds and polynomial identity testing, Article 35, 29 p. [Zbl 1380.68201]

MSC:

68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q25 Analysis of algorithms and problem complexity
00B25 Proceedings of conferences of miscellaneous specific interest

Citations:

Zbl 1329.68038
PDFBibTeX XMLCite
Full Text: Link Link