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 W. 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. - Shuichi Hirahara:
Non-black-box Worst-case to Average-case Reductions within NP. - Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. - Ilan Komargodski, Ran Raz, Yael Tauman Kalai:
A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. - Sandip Sinha, Omri Weinstein:
Local Decodability of the Burrows-Wheeler Transform. - Kaave Hosseini, Shachar Lovett:
A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds. - Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. - Mert Saglam:
Near log-convexity of measured heat in (discrete) time and consequences. - Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. - Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari:
Shortest path length with bounded-alternation (min, +) formulas. - Michael A. Forbes, Zander Kelley:
Pseudorandom Generators for Read-Once Branching Programs, in any Order. - Akash Kumar, C. Seshadhri, Andrew Stolman:
Finding forbidden minors in sublinear time: a n1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs. - Craig Gentry, Charanjit S. Jutla:
Obfuscation using Tensor Products. - Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. - Ankit Garg, Rafael Mendes de Oliveira:
Recent progress on scaling algorithms and applications. - Krishnamoorthy Dinesh, Jayalal Sarma:
Sensitivity, Affine Transforms and Quantum Communication Complexity. - Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma:
New Bounds for Energy Complexity of Boolean Functions. - Stasys Jukna, Andrzej Lingas:
Lower Bounds for Circuits of Bounded Negation Width. - Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. - Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. - Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh:
The Coin Problem in Constant Depth: Sample Complexity and Parity gates. - Igor Carboni Oliveira, Ján Pich, Rahul Santhanam:
Hardness magnification near state-of-the-art lower bounds. - Igor Carboni Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. - Anna Gál, Avishay Tal, Adrian Trejo Nuñez:
Cubic Formula Size Lower Bounds Based on Compositions with Majority. - Justin Holmgren, Ron Rothblum:
Delegating Computations with (almost) Minimal Time and Space Overhead. - Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan:
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates. - Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov:
Adventures in Monotone Complexity and TFNP. - Nikhil Gupta, Chandan Saha:
On the symmetries of design polynomials. - Stefan S. Dantchev, Nicola Galesi, Barnaby Martin:
Resolution and the binary encoding of combinatorial principles. - Tayfun Pay, James L. Cox:
An overview of some semantic and syntactic complexity classes. - Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf:
Improved bounds on Fourier entropy and Min-entropy. - Alex Samorodnitsky:
An upper bound on $\ell_q$ norms of noisy functions. - Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev:
Optimality of Linear Sketching under Modular Updates. - Nicola Galesi, Navid Talebanfard, Jacobo Torán:
Cops-Robber games and the resolution of Tseitin formulas. - Oded Goldreich:
Testing Graphs in Vertex-Distribution-Free Models. - Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan:
Building Strategies into QBF Proofs. - Eric Allender, Rahul Ilango, Neekon Vafa:
The Non-Hardness of Approximating Circuit Size. - Anastasiya Chistopolskaya, Vladimir V. Podolskii:
Parity Decision Tree Complexity is Greater Than Granularity. - Bruno Loff, Sagnik Mukhopadhyay:
Lifting Theorems for Equality. - Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif:
The Log-Approximate-Rank Conjecture is False. - Alexander Knop:
The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model. - Leroy Chew:
Hardness and Optimality in QBF Proof Systems Modulo NP. - Dominik Scheder:
PPSZ on CSP Instances with Multiple Solutions. - Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre:
Lower bounds for arithmetic circuits via the Hankel matrix. - Giuseppe Persiano, Kevin Yeo:
Lower Bounds for Differentially Private RAMs. - Henry Corrigan-Gibbs, Dmitry Kogan:
The Function-Inversion Problem: Barriers and Opportunities. - Dean Doron, Pooya Hatami, William Hoza:
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. - Iddo Tzameret, Stephen A. Cook:
Uniform, Integral and Feasible Proofs for the Determinant Identities. - Yonatan Nakar, Dana Ron:
On the Testability of Graph Partition Properties. - Emanuele Viola:
Lower bounds for data structures with space close to maximum imply circuit lower bounds. - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids. - Zeev Dvir, Alexander Golovnev, Omri Weinstein:
Static Data Structure Lower Bounds Imply Rigidity. - Ilias Diakonikolas, Daniel Kane:
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications). - Shachar Lovett, Jiapeng Zhang:
DNF sparsification beyond sunflowers. - Neeraj Kayal, Chandan Saha:
Reconstruction of non-degenerate homogeneous depth three circuits. - Alexander Golovnev, Alexander S. Kulikov:
Circuit Depth Reductions. - Nicollas M. Sdroievski, Murilo V. G. da Silva, André Luís Vignatti:
The Hidden Subgroup Problem and MKTP. - Amir Yehudayoff:
Anti-concentration in most directions. - Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma:
Erasures versus Errors in Local Decoding and Property Testing. - Omri Ben-Eliezer:
Testing local properties of arrays. - Andrej Bogdanov:
Approximate degree of AND via Fourier analysis. - Irit Dinur, Tali Kaufman, Noga Ron-Zewi:
From Local to Robust Testing via Agreement Testing. - Lijie Chen, Roei Tell:
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds. - Ashutosh Kumar, Raghu Meka, Amit Sahai:
Leakage-Resilient Secret Sharing. - Anurag Anshu, Naresh Goud Boddu, Dave Touchette:
Quantum Log-Approximate-Rank Conjecture is also False. - Xinyu Wu:
A stochastic calculus approach to the oracle separation of BQP and PH. - Yael Kalai, Dakshita Khurana:
Non-Interactive Non-Malleability from Quantum Supremacy. - Makrand Sinha, Ronald de Wolf:
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. - Siddhesh Chaubal, Anna Gál:
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity. - Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals:
Equality Alone Does Not Simulate Randomness. - Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan:
On the Probabilistic Degree of OR over the Reals. - Benny Applebaum, Prashant Nalini Vasudevan:
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe. - Emanuele Viola:
AC0 unpredictability. - Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. - Kshitij Gajjar, Jaikumar Radhakrishnan:
Parametric Shortest Paths in Planar Graphs. - Prerona Chatterjee, Ramprasad Saptharishi:
Constructing Faithful Homomorphisms over Fields of Finite Characteristic. - Moni Naor, Merav Parter, Eylon Yogev:
The Power of Distributed Verifiers in Interactive Proofs.
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-26 18:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
