Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Benjamin Rossman |
Criticality of Regular Formulas. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Coudron, Aram W. Harrow |
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Shachar Lovett, Noam Solomon, Jiapeng Zhang |
From DNF Compression to Sunflower Theorems via Regularity. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Lijie Chen 0001, Dylan M. McKay, Cody D. Murray, R. Ryan Williams |
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Mitali Bafna, Nikhil Vyas 0001 |
Imperfect Gaps in Gap-ETH and PCPs. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann, Nick Fischer, Marvin Künnemann |
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sumegha Garg, Ran Raz, Avishay Tal |
Time-Space Lower Bounds for Two-Pass Learning. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Amey Bhangale, Subhash Khot |
UG-Hardness to NP-Hardness by Losing Half. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | François Le Gall |
Average-Case Quantum Advantage with Shallow Circuits. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Stefan S. Dantchev, Nicola Galesi, Barnaby Martin |
Resolution and the Binary Encoding of Combinatorial Principles. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan 0001 |
Parity Helps to Compute Majority. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Coudron, William Slofstra |
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Lijie Chen 0001, R. Ryan Williams |
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Eshan Chattopadhyay, Anindya De, Rocco A. Servedio |
Simple and Efficient Pseudorandom Generators from Gaussian Processes. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Igor Carboni Oliveira, Ján Pich, Rahul Santhanam |
Hardness Magnification near State-Of-The-Art Lower Bounds. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals |
Equality Alone Does not Simulate Randomness. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Chin Ho Lee |
Fourier Bounds and Pseudorandom Generators for Product Tests. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Matthias Christandl, Péter Vrana, Jeroen Zuiddam |
Barriers for Fast Matrix Multiplication from Irreversibility. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Zeev Dvir, Allen Liu |
Fourier and Circulant Matrices Are Not Rigid. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev |
Optimality of Linear Sketching Under Modular Updates. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Dean Doron, Pooya Hatami, William M. Hoza |
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Nader H. Bshouty |
Almost Optimal Distribution-Free Junta Testing. |
CCC |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Anand Natarajan, Thomas Vidick |
Two-Player Entangled Games are NP-Hard. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Sampath Kannan, Elchanan Mossel, Swagato Sanyal, Grigory Yaroslavtsev |
Linear Sketching over F_2. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh |
Complexity Classification of Conjugated Clifford Circuits. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Nicolas Resch, Chaoping Xing |
Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov 0001 |
Reordering Rule Makes OBDD Proof Systems Stronger. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Omer Reingold, Guy N. Rothblum, Ron D. Rothblum |
Efficient Batch Verification for UP. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Kane 0001, Sankeerth Rao |
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Chi-Ning Chou, Mrinal Kumar 0001, Noam Solomon |
Hardness vs Randomness for Bounded Depth Arithmetic Circuits. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Zeyu Guo 0001, Nitin Saxena 0001, Amit Sinhababu |
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Richard Ryan Williams |
Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Mrinal Kumar 0001, Ben Lee Volk |
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Badih Ghazi, Pritish Kamath, Prasad Raghavendra |
Dimension Reduction for Polynomials over Gaussian Space and Applications. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Alessandro Chiesa, Peter Manohar, Igor Shinkar |
Testing Linearity against Non-Signaling Strategies. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf |
Worst-Case to Average Case Reductions for the Distance to a Code. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin |
Hardness Amplification for Non-Commutative Arithmetic Circuits. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Rocco A. Servedio (eds.) |
33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA |
CCC |
2018 |
DBLP BibTeX RDF |
|
1 | Lukas Fleischer |
On the Complexity of the Cayley Semigroup Membership Problem. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, Jiapeng Zhang |
A Tight Lower Bound for Entropy Flattening. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich |
The Power of Natural Properties as Oracles. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Andrzej Lingas |
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Omri Ben-Eliezer, Eldar Fischer |
Earthmover Resilience and Testing in Ordered Structures. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao 0001 |
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett |
Pseudorandom Generators from Polarizing Random Walks. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Watson 0001 |
Communication Complexity with Small Advantage. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Shuichi Hirahara, Igor C. Oliveira, Rahul Santhanam |
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Grier, Luke Schaeffer |
New Hardness Results for the Permanent Using Linear Optics. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi |
Hardness of Function Composition for Semantic Read once Branching Programs. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li 0006, Amnon Ta-Shma |
A New Approach for Constructing Low-Error, Two-Source Extractors. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Lijie Chen 0001 |
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. |
CCC |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Clément L. Canonne, Tom Gur |
An Adaptivity Hierarchy Theorem for Property Testing. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Elad Haramaty, Chin Ho Lee, Emanuele Viola |
Bounded Independence Plus Noise Fools Products. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Avishay Tal |
Tight Bounds on the Fourier Spectrum of AC0. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson, Lijie Chen 0001 |
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | |
Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Shuichi Hirahara, Rahul Santhanam |
On the Average-Case Complexity of MCSP and Its Variants. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam |
On Algebraic Branching Programs of Small Width. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mrinalkanti Ghosh, Madhur Tulsiani |
From Weak to Strong LP Gaps for All CSPs. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ashwin Nayak 0001, Dave Touchette |
Augmented Index and Quantum Streaming Algorithms for DYCK(2). |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Eric Blais, Clément L. Canonne, Tom Gur |
Distribution Testing Lower Bounds via Reductions from Communication Complexity. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Pavel Pudlák, Neil Thapen |
Random Resolution Refutations. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Dieter van Melkebeek, Gautam Prakriya |
Derandomizing Isolation in Space-Bounded Settings. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mrinal Kumar 0001, Ramprasad Saptharishi |
An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Markus Bläser, Gorav Jindal, Anurag Pandey 0001 |
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell (eds.) |
32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia |
CCC |
2017 |
DBLP BibTeX RDF |
|
1 | Danny Nguyen, Igor Pak |
The Computational Complexity of Integer Programming with Alternations. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain 0001, Robin Kothari, Troy Lee |
Separating Quantum Communication and Approximate Rank. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Aaron Potechin |
A Note on Amortized Branching Program Complexity. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Minahan, Ilya Volkovich |
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang |
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie |
Settling the Query Complexity of Non-Adaptive Junta Testing. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Alexey Milovanov, Nikolay K. Vereshchagin |
Stochasticity in Algorithmic Statistics for Polynomial Time. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Igor C. Oliveira, Rahul Santhanam |
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anindya De, Elchanan Mossel, Joe Neeman |
Noise Stability Is Computable and Approximately Low-Dimensional. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Srinivasan Arunachalam, Ronald de Wolf |
Optimal Quantum Sample Complexity of Learning Algorithms. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Roei Tell |
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Massimo Lauria, Jakob Nordström |
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Cody D. Murray, R. Ryan Williams |
Easiness Amplification and Uniform Circuit Lower Bounds. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Neeraj Kayal, Vineet Nair, Chandan Saha 0001, Sébastien Tavenas |
Reconstruction of Full Rank Algebraic Branching Programs. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mrinal Kumar 0001 |
A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Irit Dinur, Inbal Livni Navon |
Exponentially Small Soundness for the Direct Product Z-Test. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li |
Trading Information Complexity for Error. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mateus de Oliveira Oliveira, Pavel Pudlák |
Representations of Monotone Boolean Functions by Linear Programs. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Dominik Scheder, John P. Steinberger |
PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson 0001 |
Query-to-Communication Lifting for P^NP. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Nadia Benchikha, Mohamed Krim, Khaled Zeraoulia, Chafika Benzaid |
IWNetFAF: An Integrated Wireless Network Forensic Analysis Framework. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Rola Al Halaseh, Ja'far Alqatawna |
Analyzing CyberCrimes Strategies: The Case of Phishing Attack. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Wedyan Alswiti, Ja'far Alqatawna, Bashar Al-Shboul, Hossam Faris, Heba Hakh |
Users Profiling Using Clickstream Data Analysis and Classification. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Umar Mukhtar Ismail, Syed Islam, Shareeful Islam |
Towards Cloud Security Monitoring: A Case Study. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Fathiya Al Izki, George R. S. Weir |
Management Attitudes toward Information Security in Omani Public Sector Organisations. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Khulood Ali Al Zaabi |
Android Forensics: Investigating Social Networking Cybercrimes against Man-in-the-Middle Attacks. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Karen Renaud, George R. S. Weir |
Cybersecurity and the Unbearability of Uncertainty. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Aisha Zaid, Ja'far Alqatawna, Ammar Huneiti |
A Proposed Model for Malicious Spam Detection in Email Systems of Educational Institutes. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Ja'far Alqatawna, Ali Hadi, Malek Al-Zewairi, Mariam Khader |
A Preliminary Analysis of Drive-by Email Attacks in Educational Institutes. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Nazeeh Ghatasheh |
Fraud Prevention Framework for Electronic Business Environments: Automatic Segregation of Online Phishing Attempts. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Mohammad Qbea'h, Mohammad Aref Alshraideh, Khair Eddin Sabri |
Detecting and Preventing SQL Injection Attacks: A Formal Approach. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Izzat Alsmadi, Iyad Alazzam |
Websites' Input Validation and Input-Misuse-Based Attacks. |
CCC |
2016 |
DBLP DOI BibTeX RDF |
|