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.
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-12-31 21:48 CET 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:
