default search action
Computational Complexity, Volume 28
Volume 28, Number 1, March 2019
- Gillat Kol, Shay Moran, Amir Shpilka
, Amir Yehudayoff:
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. 1-25 - Matthias Christandl, Jeroen Zuiddam:
Tensor surgery and tensor rank. 27-56 - Matthias Christandl, Péter Vrana
Asymptotic tensor rank of graph tensors: beyond matrix multiplication. 57-111 - Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P NP. 113-144
Volume 28, Number 2, June 2019
- Or Meir, Avi Wigderson:
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. 145-183 - Pavel Pudlák, Neil Thapen:
Random resolution refutations. 185-239 - Anshul Adve, Colleen Robichaux
Vanishing of Littlewood-Richardson polynomials is in P. 241-257 - Roei Tell:
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. 259-343
Volume 28, Number 3, September 2019
- Jin-Yi Cai, Xi Chen:
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. 345-408 - Mrinal Kumar:
A quadratic lower bound for homogeneous algebraic branching programs. 409-435 - Martijn Baartse, Klaus Meer:
Interactive proofs and a Shamir-like result for real number computations. 437-469 - Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees. 471-542 - Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Correction to: Query-to-Communication Lifting for P NP. 543-544
Volume 28, Number 4, December 2019
- Suryajith Chillara, Partha Mukhopadhyay:
Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach. 545-572 - Benny Applebaum, Pavel Raykov:
On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings. 573-616 - Arkadev Chattopadhyay, Michal Koucký
Simulation Theorems via Pseudo-random Properties. 617-659 - Or Meir:
On Derandomized Composition of Boolean Functions. 661-708 - Oded Goldreich:
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. 709-747 - Neeraj Kayal, Vineet Nair, Chandan Saha:
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. 749-828
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-12 20: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: