


default search action
Electronic Colloquium on Computational Complexity, 2017
Volume TR17, 2017
- Stephen A. Cook, Bruce M. Kapron:
A Survey of Classes of Primitive Recursive Functions. - Frantisek Duris:
Some notes on two lower bound methods for communication complexity. - Yi Deng:
Magic Adversaries Versus Individual Reduction: Science Wins Either Way. - Scott Aaronson:
P=?NP. - Nir Bitansky:
Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs. - Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath:
Testing Ising Models. - Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. - Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan:
Low-Complexity Cryptographic Hash Functions. - Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. - Xiaodi Wu, Penghui Yao, Henry S. Yuen:
Raz-McKenzie simulation with the inner product gadget. - Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. - Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau:
Emptiness Problems for Integer Circuits. - Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan:
On polynomial approximations over ℤ/2kℤ. - Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Composition and Simulation Theorems via Pseudo-random Properties. - Ilan Komargodski, Moni Naor, Eylon Yogev:
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. - Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena:
Irreducibility and deterministic r-th root finding over finite fields. - Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Lower Bounds for Space Bounded Learning. - Oded Goldreich, Guy N. Rothblum:
Simple doubly-efficient interactive proof systems for locally-characterizable sets. - Andreas Krebs, Nutan Limaye, Michael Ludwig:
A Unified Method for Placing Problems in Polylogarithmic Depth. - Ran Raz:
A Time-Space Lower Bound for a Large Class of Learning Problems. - Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of full rank Algebraic Branching Programs. - Benjamin Rossman, Srikanth Srinivasan:
Separation of AC0[⊕] Formulas and Circuits. - Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. - Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. - Pooya Hatami, Avishay Tal:
Pseudorandom Generators for Low-Sensitivity Functions. - Valentine Kabanets, Daniel M. Kane, Zhenjian Lu:
A Polynomial Restriction Lemma with Applications. - Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma:
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate. - Mrinal Kumar:
A quadratic lower bound for homogeneous algebraic branching programs. - Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. - Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari:
An Improved Dictatorship Test with Perfect Completeness. - Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. - Olaf Beyersdorff, Joshua Blinkhorn:
Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds. - Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. - Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On algebraic branching programs of small width. - Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. - Dean Doron, Francois Le Gall, Amnon Ta-Shma:
Probabilistic logarithmic-space algorithms for Laplacian solvers. - Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla:
Understanding Cutting Planes for QBFs. - Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan:
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations. - Marshall Ball
, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan:
Average-Case Fine-Grained Hardness. - Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao:
Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers. - Amnon Ta-Shma:
Explicit, almost optimal, epsilon-balanced codes. - Pavel Hrubes, Pavel Pudlák:
Random formulas, monotone circuits, and interpolation. - Alexey Milovanov, Nikolai K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. - Olaf Beyersdorff, Luke Hinde, Ján Pich:
Reasons for Hardness in QBF Proof Systems. - Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random CNFs are Hard for Cutting Planes. - Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata. - Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. - Pavel Hrubes, Pavel Pudlák:
A note on monotone real circuits. - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. - Joe Boninger, Joshua Brody, Owen Kephart:
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search. - Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. - Dieter van Melkebeek, Gautam Prakriya:
Derandomizing Isolation in Space-Bounded Settings. - Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. - Anurag Anshu, Naresh B. Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay:
Lifting randomized query complexity to randomized communication complexity. - Maya Leshkowitz:
Round Complexity Versus Randomness Complexity in Interactive Proofs. - Paul W. Goldberg, Christos H. Papadimitriou:
Towards a Unified Complexity Theory of Total Functions. - Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:
A Zero Knowledge Sumcheck and its Applications. - Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing hereditary properties of ordered graphs and matrices. - Ola Svensson, Jakub Tarnawski:
The Matching Problem in General Graphs is in Quasi-NC. - Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari:
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). - Anat Ganor, Karthik C. S.:
Communication Complexity of Correlated Equilibrium in Two-Player Games. - Arkadev Chattopadhyay, Nikhil S. Mande:
Dual polynomials and communication complexity of XOR functions. - Benny Applebaum:
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions. - Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
Subspace Designs based on Algebraic Function Fields. - Boaz Barak:
The Complexity of Public-Key Cryptograph. - Josh Alman, Joshua R. Wang, Huacheng Yu:
Cell-Probe Lower Bounds from Online Communication Complexity. - Benny Applebaum:
Garbled Circuits as Randomized Encodings of Functions: a Primer. - Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. - Jacob Steinhardt:
Does robustness imply tractability? A lower bound for planted clique in the semi-random model. - Shachar Lovett, Sankeerth Rao, Alexander Vardy:
Probabilistic Existence of Large Sets of Designs. - Young Kun-Ko, Ariel Schvartzman:
Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria. - Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Machines. - Eric Allender, Shuichi Hirahara:
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. - Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S:
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings. - Clément L. Canonne, Ilias Diakonikolas, Alistair Stewart:
Fourier-Based Testing for Families of Distributions. - Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee:
New Protocols for Conditional Disclosure of Secrets (and More). - Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan:
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees. - Nico Döttling, Jesper Buus Nielsen, Maciej Obremski:
Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model. - Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. - Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. - Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. - Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. - Arkadev Chattopadhyay, Nikhil S. Mande:
Weights at the Bottom Matter When the Top is Heavy. - Iftach Haitner, Salil P. Vadhan:
The Many Entropies in One-Way Functions. - Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. - C. Ramya, B. V. Raghavendra Rao:
Linear Projections of the Vandermonde Polynomial. - Pushkar S. Joglekar, B. V. Raghavendra Rao, Siddharth S. Sivakumar:
On Weak-Space Complexity over Complex Numbers. - Elena Grigorescu, Akash Kumar, Karl Wimmer:
K-Monotonicity is Not Testable on the Hypercube. - Irit Dinur, Tali Kaufman:
High dimensional expanders imply agreement expanders. - Chin Ho Lee, Emanuele Viola:
The coin problem for product tests. - Andrej Bogdanov:
Small bias requires large formulas. - Shuichi Hirahara:
A Duality Between Depth-Three Formulas and Approximation by Depth-Two. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Coding Over the Noisy Broadcast Channel. - Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
:
On Non-Optimally Expanding Sets in Grassmann Graphs. - Ran Gelles, Yael Tauman Kalai:
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. - Irit Dinur, Inbal Livni Navon:
Exponentially Small Soundness for the Direct Product Z-test. - Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan:
Multi Collision Resistant Hash Functions and their Applications. - Raman Arora, Amitabh Basu, Poorya Mianjy, Anirbit Mukherjee:
Understanding Deep Neural Networks with Rectified Linear Units. - Nir Bitansky, Omer Paneth, Yael Tauman Kalai:
Multi-Collision Resistance: A Paradigm for Keyless Hash Functions. - Dakshita Khurana, Amit Sahai:
How to Achieve Non-Malleability in One or Two Rounds. - Oded Goldreich:
On the doubly-efficient interactive proof systems of GKR. - Oded Goldreich:
Overview of the doubly-efficient interactive proof systems of RRR. - Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. - Brett Hemenway, Noga Ron-Zewi, Mary Wootters:
Local List Recovery of High-rate Tensor Codes & Applications. - Shafi Goldwasser, Ofer Grossman, Dhiraj Holden:
Pseudo-Deterministic Proofs. - Mateus de Oliveira Oliveira, Pavel Pudlák:
Representations of Monotone Boolean Functions by Linear Programs. - Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query complexity. - Shafi Goldwasser, Guy N. Rothblum, Yael Tauman Kalai:
Delegating Computation: Interactive Proofs for Muggles. - Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help? - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. - Yehuda Lindell:
How To Simulate It - A Tutorial on the Simulation Proof Technique. - Andrej Bogdanov, Alon Rosen:
Pseudorandom Functions: Three Decades Later. - Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Proper Learning of k-term DNF Formulas from Satisfying Assignments. - Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket:
Hardness of learning noisy halfspaces using polynomial thresholds. - Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Strong Lower Bounds for Space Bounded Learning. - Dmitry Itsykson, Alexander Knop:
Hard satisfiable formulas for splittings by linear combinations. - Xiaotie Deng, Zhe Feng, Rucha Kulkarni:
Octahedral Tucker is PPA-Complete. - Badih Ghazi, T. S. Jayram:
Resource-Efficient Common Randomness and Secret-Key Schemes. - Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. - Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. - Rohit Gurjar, Ben Lee Volk:
Pseudorandom Bits for Oblivious Branching Programs. - Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. - Mrinal Kumar, Ben Lee Volk:
An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. - Badih Ghazi, Pritish Kamath, Prasad Raghavendra:
Dimension Reduction for Polynomials over Gaussian Space and Applications. - Swastik Kopparty, Shubhangi Saraf:
Local Testing and Decoding of High-Rate Error-Correcting Codes. - Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. - Or Meir:
The Direct Sum of Universal Relations. - Or Meir:
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds. - Oded Goldreich, Guy N. Rothblum:
Worst-case to Average-case reductions for subclasses of P. - Joshua A. Grochow, Cristopher Moore:
Designing Strassen's algorithm. - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Sharp Bounds for Generalized Uniformity Testing. - Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price:
Sample-Optimal Identity Testing with High Probability. - Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev:
Fast Reed-Solomon Interactive Oracle Proofs of Proximity. - Ramprasad Saptharishi, Anamay Tengse:
Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees. - Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo:
Complete Classi fication of Generalized Santha-Vazirani Sources. - Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde:
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs. - Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids. - Thomas Watson:
A ZPP^NP[1] Lifting Theorem. - Tong Qin, Osamu Watanabe:
An improvement of the algorithm of Hertli for the unique 3SAT problem.