ask others

Electronic Colloquium on Computational Complexity, Volume 23

Name: dblp XML data dump
Creator: Schloss Dagstuhl - Leibniz Center for Informatics
License: https://opendatacommons.org/licenses/by/1.0/
Keywords: dblp, XML, computer science, scholarly publications, metadata

> Home > Journals > Electronic Colloquium on Computational Complexity

Volume 23, 2016

- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonCGV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonCGV16
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza:
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs. 1
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Williams16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Williams16
Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. 2
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BrimkovH16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BrimkovH16
Boris Brimkov, Illya V. Hicks:
On the logspace shortest path problem. 3
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Koh16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Koh16
Dax Enshan Koh:
Further extensions of Clifford circuits and their classical simulation complexities. 4
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeyersdorffCJ16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeyersdorffCJ16
Olaf Beyersdorff, Leroy Chew, Mikolas Janota:
Extension Variables in QBF Resolution. 5
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KayalST16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KayalST16
Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits. 6
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Kindler16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Kindler16
Guy Kindler:
Property Testing, PCP, andJuntas. 7
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CarmosinoIKK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CarmosinoIKK16
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Algorithms from Natural Lower Bounds. 8
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GurjarKS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GurjarKS16
Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Identity Testing for constant-width, and commutative, read-once oblivious ABPs. 9
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Razborov16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Razborov16
Alexander A. Razborov:
On the Width of Semi-Algebraic Proofs and Algorithms. 10
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeyersdorffP16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeyersdorffP16
Olaf Beyersdorff, Ján Pich:
Understanding Gentzen and Frege systems for QBF. 11
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HitchcockS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HitchcockS16
John M. Hitchcock, Hadi Shafei:
Autoreducibility of NP-Complete Sets. 12
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Staiger16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Staiger16
Ludwig Staiger:
Bounds on the Kolmogorov complexity function for infinite words. 13
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CohenS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CohenS16
Gil Cohen, Leonard J. Schulman:
Extractors for Near Logarithmic Min-Entropy. 14
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Goldreich16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Goldreich16
Oded Goldreich:
The uniform distribution is complete with respect to testing identity to a fixed distribution. 15
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LiuPZKA16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LiuPZKA16
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson:
Doubly infinite separation of quantum information and communication. 16
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Stamoulis16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Stamoulis16
Georgios Stamoulis:
Limitations of Linear Programming Techniques for Bounded Color Matchings. 17
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChengL16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChengL16
Kuan Cheng, Xin Li:
Randomness Extraction in AC⁰ and with Small Locality. 18
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Raz16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Raz16
Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. 19
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Remscrim16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Remscrim16
Zachary Remscrim:
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. 20
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LovettZ16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LovettZ16
Shachar Lovett, Jiapeng Zhang:
Noisy Population Recovery from Unknown Noise. 21
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GolovnevKST16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GolovnevKST16
Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki:
Circuit size lower bounds and #SAT upper bounds through a general framework. 22
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KomargodskiNY16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KomargodskiNY16
Ilan Komargodski, Moni Naor, Eylon Yogev:
How to Share a Secret, Infinitely. 23
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ScharpfeneckerT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ScharpfeneckerT16
Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. 24
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Lovett16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Lovett16
Shachar Lovett:
The Fourier structure of low degree polynomials. 25
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DeST16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DeST16
Anindya De, Michael E. Saks, Sijian Tang:
Noisy population recovery in polynomial time. 26
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Mukhopadhyay16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Mukhopadhyay16
Sagnik Mukhopadhyay:
Tribes Is Hard in the Message Passing Model. 27
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeyersdorffB16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeyersdorffB16
Olaf Beyersdorff, Joshua Blinkhorn:
Dependency Schemes in QBF Calculi: Semantics and Soundness. 28
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BrakensiekG16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BrakensiekG16
Joshua Brakensiek, Venkatesan Guruswami:
New hardness results for graph and hypergraph colorings. 29
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Cohen16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Cohen16
Gil Cohen:
Non-Malleable Extractors with Logarithmic Seeds. 30
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Dose16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Dose16
Titus Dose:
Complexity of Constraint Satisfaction Problems over Finite Substsets of Natural Numbers. 31
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Tell16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Tell16
Roei Tell:
A Note on Tolerant Testing with One-Sided Error. 32
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GuruswamiR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GuruswamiR16
Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight bounds for communication assisted agreement distillation. 33
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Halaby16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Halaby16
Mohamed El Halaby:
On the Computational Complexity of MaxSAT. 34
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DinurM16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DinurM16
Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. 35
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayL16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayL16
Eshan Chattopadhyay, Xin Li:
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. 36
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ArtemenkoIKS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ArtemenkoIKS16
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness when the odds are against you. 37
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/MahajanS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/MahajanS16
Meena Mahajan, Nitin Saurabh:
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. 38
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BoulandMZ16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BoulandMZ16
Adam Bouland, Laura Mancinska, Xue Zhang:
Complexity Classification of Two-Qubit Commuting Hamiltonians. 39
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AydinliogluB16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AydinliogluB16
Baris Aydinlioglu, Eric Bach:
Affine Relativization: Unifying the Algebrization and Relativization Barriers. 40
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Hastad16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Hastad16
Johan Håstad:
An average-case depth hierarchy theorem for higher depth. 41
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GoldreichG16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GoldreichG16
Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. 42
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Janota16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Janota16
Mikolas Janota:
On Q-Resolution and CDCL QBF Solving. 43
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HosseiniL16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HosseiniL16
Kaave Hosseini, Shachar Lovett:
Structure of protocols for XOR functions. 44
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ForbesKS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ForbesKS16
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. 45
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonCGRS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonCGRS16
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck. 46
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BavarianVY16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BavarianVY16
Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel repetition via fortification: analytic view and the quantum case. 47
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BeyersdorffCSS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BeyersdorffCSS16
Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda:
Lifting QBF Resolution Calculi to DQBF. 48
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DworkNR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DworkNR16
Cynthia Dwork, Moni Naor, Guy N. Rothblum:
Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems. 49
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Tell16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Tell16a
Roei Tell:
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. 50
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CramerXY16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CramerXY16
Ronald Cramer, Chaoping Xing, Chen Yuan:
On Multi-Point Local Decoding of Reed-Muller Codes. 51
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Cohen16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Cohen16a
Gil Cohen:
Making the Most of Advice: New Correlation Breakers and Their Applications. 52
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GaoI16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GaoI16
Jiawei Gao, Russell Impagliazzo:
Orthogonal Vectors is hard for first-order properties on sparse graphs. 53
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/WeinsteinY16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/WeinsteinY16
Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. 54
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/RoughgardenW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/RoughgardenW16
Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. 55
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GoldwasserH16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GoldwasserH16
Shafi Goldwasser, Dhiraj Holden:
On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances. 56
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Bonacina16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Bonacina16
Ilario Bonacina:
Total space in Resolution is at least width squared. 57
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BarakHKKMP16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BarakHKKMP16
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. 58
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/RosenSS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/RosenSS16
Alon Rosen, Gil Segev, Ido Shahaf:
Can PPAD Hardness be Based on Standard Cryptographic Assumptions? 59
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Yuen16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Yuen16
Henry Yuen:
A parallel repetition theorem for all entangled games. 60
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ReingoldRR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ReingoldRR16
Omer Reingold, Ron Rothblum, Guy N. Rothblum:
Constant-Round Interactive Proofs for Delegating Computation. 61
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Tal16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Tal16
Avishay Tal:
On The Sensitivity Conjecture. 62
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HubacekY16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HubacekY16
Pavel Hubácek, Eylon Yogev:
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. 63
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CookPRR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CookPRR16
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman:
Exponential Lower Bounds for Monotone Span Programs. 64
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenCT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenCT16
Xi Chen, Yu Cheng, Bo Tang:
A Note on Teaching for VC Classes. 65
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Goldreich16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Goldreich16a
Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. 66
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KomarathSS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KomarathSS16
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani:
Pebbling Meets Coloring : Reversible Pebble Game On Trees. 67
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Srinivasan16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Srinivasan16
Srikanth Srinivasan:
On Polynomial Approximations to AC⁰. 68
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GopalanSTW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GopalanSTW16
Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. 69
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GoosJW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GoosJW16
Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. 70
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KrajicekO16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KrajicekO16
Jan Krajícek, Igor Carboni Oliveira:
Unprovability of circuit upper bounds in Cook's theory PV. 71
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AnshuBBGJKLS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AnshuBBGJKLS16
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. 72
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-SassonBGR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-SassonBGR16
Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev:
Improved concrete efficiency and security analysis of Reed-Solomon PCPPs. 73
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DiakonikolasK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DiakonikolasK16
Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. 74
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BunT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BunT16
Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC⁰. 75
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KrishnamoorthyK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KrishnamoorthyK16
Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma:
Characterization and Lower Bounds for Branching Program Size using Projective Dimension. 76
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BrakerskiHK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BrakerskiHK16
Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai:
Non-Interactive RAM and Batch NP Delegation from any PIR. 77
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ValiantV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ValiantV16
Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. 78
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KurpiszLM16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KurpiszLM16
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli:
Sum-of-squares hierarchy lower bounds for symmetric formulations. 79
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Goldreich16b
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Goldreich16b
Oded Goldreich:
Reducing testing affine spaces to testing linearity. 80
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Sherstov16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Sherstov16
Alexander A. Sherstov:
Compressing interactive communication under product distributions. 81
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ApplebaumR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ApplebaumR16
Benny Applebaum, Pavel Raykov:
Fast Pseudorandom Functions Based on Expander Graphs. 82
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Bshouty16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Bshouty16
Nader H. Bshouty:
Derandomizing Chernoff Bound with Union Bound with an Application to k-wise Independent Sets. 83
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-David16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-David16
Shalev Ben-David:
Low-Sensitivity Functions from Unambiguous Certificates. 84
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenP16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenP16
Shiteng Chen, Periklis A. Papakonstantinou:
Depth-reduction for composites. 85
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AlonES16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AlonES16
Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. 86
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-DavidK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-DavidK16
Shalev Ben-David, Robin Kothari:
Randomized query complexity of sabotaged and composed functions. 87
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-AroyaDT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-AroyaDT16
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Explicit two-source extractors for near-logarithmic min-entropy. 88
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ArvindMS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ArvindMS16
Vikraman Arvind, Partha Mukhopadhyay, Raja S:
Randomized Polynomial Time Identity Testing for Noncommutative Circuits. 89
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HaeuplerV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HaeuplerV16
Bernhard Haeupler, Ameya Velingker:
Bridging the Capacity Gap Between Interactive and One-Way Communication. 90
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BitanskyDV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BitanskyDV16
Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan:
Structure vs Hardness through the Obfuscation Lens. 91
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/AsharovRS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/AsharovRS16
Gilad Asharov, Alon Rosen, Gil Segev:
Indistinguishability Obfuscation Does Not Reduce to Structured Languages. 92
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Rashtchian16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Rashtchian16
Cyrus Rashtchian:
Bounded Matrix Rigidity and John's Theorem. 93
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LagardeMP16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LagardeMP16
Guillaume Lagarde, Guillaume Malod, Sylvain Perifel:
Non-commutative computations: lower bounds and polynomial identity testing. 94
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayM16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayM16
Arkadev Chattopadhyay, Nikhil S. Mande:
Small Error Versus Unbounded Error Protocols in the NOF Model. 95
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChillaraKSV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChillaraKSV16
Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V. Vinay:
The Chasm at Depth Four, and Tensor Rank : Old results, new insights. 96
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KallampallyT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KallampallyT16
Vivek Anand T. Kallampally, Raghunath Tewari:
Trading Determinism for Time in Space Bounded Computations. 97
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ForbesSTW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ForbesSTW16
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. 98
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SakaiSTT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SakaiSTT16
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama:
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. 99
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Tamaki16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Tamaki16
Suguru Tamaki:
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates. 100
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/PitassiT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/PitassiT16
Toniann Pitassi, Iddo Tzameret:
Algebraic Proof Complexity: Progress, Frontiers and Challenges. 101
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BoppanaHLV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BoppanaHLV16
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. 102
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/RadhakrishnanS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/RadhakrishnanS16
Jaikumar Radhakrishnan, Swagato Sanyal:
The zero-error randomized query complexity of the pointer function. 103
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GhaziKS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GhaziKS16
Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-Interactive Simulation of Joint Distributions. 104
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BlaisCELR16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BlaisCELR16
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. 105
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Ben-AroyaDT16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Ben-AroyaDT16a
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Low-error two-source extractors for polynomial min-entropy. 106
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Fijalkow16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Fijalkow16
Nathanaël Fijalkow:
Lower Bounds for Alternating Online Space Complexity. 107
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Rudow16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Rudow16
Michael Rudow:
Discrete Logarithm and Minimum Circuit Size. 108
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Aaronson16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Aaronson16
Scott Aaronson:
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. 109
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GolovnevRW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GolovnevRW16
Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. 110
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabartiK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabartiK16
Amit Chakrabarti, Sagar Kale:
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics. 111
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/HajiaghayiBGKK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HajiaghayiBGKK16
Mohammad Taghi Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz:
Bicovering: Covering edges with two small subsets of vertices. 112
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KolRT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KolRT16
Gillat Kol, Ran Raz, Avishay Tal:
Time-Space Hardness of Learning Sparse Parities. 113
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Cohen16b
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Cohen16b
Gil Cohen:
Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols. 114
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Li16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Li16
Xin Li:
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors. 115
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KhotS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KhotS16
Subhash Khot, Rishi Saket:
Approximating CSPs using LP Relaxation. 116
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GhoshT16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GhoshT16
Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for all CSPs. 117
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/LovettZ16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/LovettZ16a
Shachar Lovett, Jiapeng Zhang:
On the impossibility of entropy reversal, and its application to zero-knowledge proofs. 118
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GolovnevHKK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GolovnevHKK16
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov:
On the Limits of Gate Elimination. 119
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/DoronST16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/DoronST16
Dean Doron, Amir Sarid, Amnon Ta-Shma:
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. 120
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BunT16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BunT16a
Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. 121
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GopiKORS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GopiKORS16
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf:
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound. 122
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Jukna16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Jukna16
Stasys Jukna:
Tropical Complexity, Sidon Sets, and Dynamic Programming. 123
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Khot16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Khot16
Subhash Khot, Dor Minzer, Muli Safra:
On Independent Sets, 2-to-2 Games and Grassmann Graphs. 124
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChandrasekaranC16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChandrasekaranC16
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu:
Local Testing for Membership in Lattices. 125
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/KhotS16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/KhotS16a
Subhash Khot, Igor Shinkar:
An Õ(n) Queries Adaptive Tester for Unateness. 126
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/GowersV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/GowersV16
Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. 127
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Dinur16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Dinur16
Irit Dinur:
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. 128
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ViolaW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ViolaW16
Emanuele Viola, Avi Wigderson:
Local Expanders. 129
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayLL16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayLL16
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra:
Tight Network Topology Dependent Bounds on Rounds of Communication. 130
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BogdanovGK16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BogdanovGK16
Andrej Bogdanov, Siyao Guo, Ilan Komargodski:
Threshold Secret Sharing Requires a Linear Size Alphabet. 131
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BafnaLTV16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BafnaLTV16
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker:
On the Sensitivity Conjecture for Read-k Formulas. 132
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabartyS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabartyS16
Deeparnab Chakrabarty, C. Seshadhri:
A Õ(n) Non-Adaptive Tester for Unateness. 133
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ShaltielS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ShaltielS16
Ronen Shaltiel, Jad Silbak:
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. 134
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BerkholzN16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BerkholzN16
Christoph Berkholz, Jakob Nordström:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. 135
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/CanonneGGKW16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/CanonneGGKW16
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer:
Testing k-Monotonicity. 136