Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2018
Volume TR18, 2018
- Tim Roughgarden:
Complexity Theory, Game Theory, and Economics.
- Constantinos Daskalakis, Gautam Kamath, John Wright:
Which Distribution Distances are Sublinearly Testable? - Roei Tell:
Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP. - Aayush Ojha, Raghunath Tewari:
Circuit Complexity of Bounded Planar Cutwidth Graph Matching. - Deeparnab Chakrabarty, C. Seshadhri:
Adaptive Boolean Monotonicity Testing in Total Influence Time. - Subhash Khot, Dor Minzer, Muli Safra:
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. - Lior Gishboliner, Asaf Shapira:
A Generalized Turan Problem and its Applications. - Tom Gur, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. - Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs:
Non-Interactive Delegation for Low-Space Non-Deterministic Computation. - Alexander A. Sherstov:
Algorithmic polynomials. - John M. Hitchcock, Hadi Shafei:
Nonuniform Reductions and NP-Completeness. - Valentine Kabanets, Zhenjian Lu:
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates. - John M. Hitchcock, Adewale Sekoni:
Nondeterminisic Sublinear Time Has Measure 0 in P. - Swagato Sanyal:
A Composition Theorem via Conflict Complexity. - Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett:
Pseudorandom Generators from Polarizing Random Walks. - Naomi Kirshner, Alex Samorodnitsky:
On ℓ4: ℓ2 ratio of functions with restricted Fourier support. - Venkatesan Guruswami, Nicolas Resch, Chaoping Xing:
Lossless dimension expanders via linearized polynomials and subspace designs. - John M. Hitchcock, Adewale Sekoni, Hadi Shafei:
Polynomial-Time Random Oracles and Separating Complexity Classes. - Zeyu Guo, Nitin Saxena, Amit Sinhababu:
Algebraic dependencies and PSPACE algorithms in approximative complexity. - Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari:
Computing the maximum using (min, +) formulas. - Omri Ben-Eliezer, Eldar Fischer:
Earthmover Resilience and Testing in Ordered Structures. - Omer Reingold, Guy N. Rothblum, Ron Rothblum:
Efficient Batch Verification for UP. - Eran Iceland, Alex Samorodnitsky:
On coset leader graphs of structured linear codes. - Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
:
The Riis Complexity Gap for QBF Resolution. - Olaf Beyersdorff, Judith Clymo:
More on Size and Width in QBF Resolution. - Lijie Chen:
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. - Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. - Xin Li:
Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications. - Neeraj Kayal, Vineet Nair, Chandan Saha:
Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs. - Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam:
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. - Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff:
On the Communication Complexity of Key-Agreement Protocols. - Gil Cohen, Bernhard Haeupler, Leonard J. Schulman:
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet. - Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz:
The Communication Complexity of Private Simultaneous Messages, Revisited. - Young Kun Ko:
On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG. - Manindra Agrawal, Sumanta Ghosh, Nitin Saxena:
Bootstrapping variables in algebraic circuits. - Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Towards blackbox identity testing of log-variate circuits. - Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p→q Norms. - Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann:
Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees. - Md Lutfar Rahman, Thomas Watson:
Complexity of Unordered CNF Games. - Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. - Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Reordering Rule Makes OBDD Proof Systems Stronger. - Stasys Jukna:
Incremental versus Non-Incremental Dynamic Programming. - Andrei E. Romashchenko, Marius Zimand:
An operational characterization of mutual information in algorithmic information theory. - Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. - Oded Goldreich, Dana Ron:
The Subgraph Testing Model. - Oded Goldreich, Guy N. Rothblum:
Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems. - Shachar Lovett:
A proof of the GM-MDS conjecture. - Ofer Grossman, Yang P. Liu:
Reproducibility and Pseudo-Determinism in Log-Space. - Stasys Jukna, Hannes Seiwert:
Greedy can also beat pure dynamic programming. - Irit Dinur, Oded Goldreich, Tom Gur:
Every set in P is strongly testable under a suitable encoding. - Stasys Jukna:
Derandomizing Dynamic Programming and Beyond. - Chi-Ning Chou, Mrinal Kumar, Noam Solomon:
Some Closure Results for Polynomial Factorization and Applications. - Nader H. Bshouty:
Lower Bound for Non-Adaptive Estimate the Number of Defective Items. - Klim Efremenko, Elad Haramaty, Yael Kalai:
Interactive Coding with Constant Round and Communication Blowup. - Titus Dose:
Balance Problems for Integer Circuits. - Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs:
Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing. - Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi:
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. - Thomas Watson:
Amplification with One NP Oracle Query. - Joshua Brakensiek, Venkatesan Guruswami:
Combining LPs and Ring Equations via Structured Polymorphisms. - Emanuele Viola:
Sampling lower bounds: boolean average-case and permutations. - Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. - Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan:
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. - William Hoza, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. - Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov:
Generalized Matrix Completion and Algebraic Natural Proofs. - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends. - Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma:
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Testing Linearity against Non-Signaling Strategies. - Mrinal Kumar:
On top fan-in vs formal degree for depth-3 arithmetic circuits. - Oded Goldreich, Guy N. Rothblum:
Constant-round interactive proof systems for AC0[2] and NC1. - Eshan Chattopadhyay, Xin Li:
Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More. - Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak:
Computational Two-Party Correlation. - Avi Wigderson:
On the nature of the Theory of Computation (ToC). - Amey Bhangale:
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. - Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized comparison trees for point-location problems. - Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha:
Boolean function analysis on high-dimensional expanders. - Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao:
Torus polynomials: an algebraic approach to ACC lower bounds. - Boaz Barak, Pravesh Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. - Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra:
Small Set Expansion in The Johnson Graph. - Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi:
Distributed Simulation and Distributed Inference. - Moritz Gobbert:
Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games. - Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar:
On Multilinear Forms: Bias, Correlation, and Tensor Rank. - Xin Li, Shachar Lovett, Jiapeng Zhang:
Sunflowers and Quasi-sunflowers from Randomness Extractors. - Tom Gur, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. - Iftach Haitner, Nikolaos Makriyannis, Eran Omri:
On the Complexity of Fair Coin Flipping. - Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan:
XOR Codes and Sparse Random Linear Equations with Noise. - Joseph Swernofsky:
Tensor Rank is Hard to Approximate. - Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang:
Quantum Lovász Local Lemma: Shearer's Bound is Tight. - Ilya Volkovich:
A story of AM and Unique-SAT. - Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal:
Half-duplex communication complexity. - Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf:
Worst-case to average case reductions for the distance to a code. - Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters:
Improved decoding of Folded Reed-Solomon and Multiplicity Codes. - Marco Carmosino, Russell Impagliazzo, Manuel Sabin:
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. - Irit Dinur, Pasin Manurangsi:
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. - Amit Levi, Erik Waingarten:
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. - Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. - Venkatesan Guruswami, Andrii Riazanov:
Beating Fredman-Komlós for perfect k-hashing. - Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximating Operator Norms via Generalized Krivine Rounding. - Oded Goldreich:
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. - Scott Aaronson:
PDQP/qpoly = ALL. - Eshan Chattopadhyay, Anindya De, Rocco A. Servedio:
Simple and efficient pseudorandom generators from Gaussian processes. - Akash Kumar, C. Seshadhri, Andrew Stolman:
Finding forbidden minors in sublinear time: a O(n1/2+o(1))-query one-sided tester for minor closed properties on bounded degree graphs. - Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan:
Short Proofs in QBF Expansion. - Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. - Oded Goldreich:
Flexible models for testing graph properties. - Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen:
Quantum proof systems for iterated exponential time, and beyond. - Chetan Gupta, Vimalraj Sharma, Raghunath Tewari:
Reachability in O(log n) Genus Graphs is in Unambiguous. - Ran Raz, Avishay Tal:
Oracle Separation of BQP and PH. - Andrzej Lingas:
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth. - Kasper Green Larsen, Jesper Buus Nielsen:
Yes, There is an Oblivious RAM Lower Bound! - Fu Li, David Zuckerman:
Improved Extractors for Recognizable and Algebraic Sources. - Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay:
Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits. - Raghu Meka, Omer Reingold, Avishay Tal:
Pseudorandom Generators for Width-3 Branching Programs. - Dominik Scheder:
PPSZ for k ≥ 5: More Is Better. - Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. - Valentine Kabanets, Zhenjian Lu:
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. - Xue Chen, David Zuckerman:
Existence of Simple Extractors. - Fedor Part, Iddo Tzameret:
Resolution with Counting: Lower Bounds over Different Moduli. - Alexander Durgin, Brendan Juba:
Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs. - Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, Jiapeng Zhang:
A Tight Lower Bound for Entropy Flattening. - Alexandros Hollender, Paul Goldberg:
The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard. - Justin Holmgren, Lisa Yang:
Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem. - Igor Carboni Oliveira, Rahul Santhanam:
Pseudo-derandomizing learning and approximation. - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing. - Amir Yehudayoff:
Separating Monotone VP and VNP. - Zvika Brakerski:
Fundamentals of Fully Homomorphic Encryption - A Survey. - Pravesh Kothari, Ruta Mehta:
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. - Stasys Jukna, Hannes Seiwert:
Approximation Limitations of Tropical Circuits. - Ewin Tang:
A quantum-inspired classical algorithm for recommendation systems. - Jelani Nelson, Huacheng Yu:
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. - Gautam Kamath, Christos Tzamos:
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing. - Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse:
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. - Emanuele Viola:
Constant-error pseudorandomness proofs from hardness require majority. - Tali Kaufman, David Mass:
Cosystolic Expanders over any Abelian Group. - Prasad Chaugule, Nutan Limaye, Aditya Varre:
Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. - Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma:
List Decoding with Double Samplers. - Scott Aaronson:
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials.