Sign in
Comput. Complex.
1991
2002
2013
2024
1991
2024
Keyphrases
Publications
volume 33, number 1, 2024
Ferenc Bencs
,
Jeroen Huijben
,
Guus Regts
Approximating the chromatic polynomial is as hard as computing it exactly.
Comput. Complex.
33 (1) (2024)
volume 32, number 1, 2023
Prasad Chaugule
,
Mrinal Kumar
,
Nutan Limaye
,
Chandra Kanta Mohapatra
,
Adrian She
,
Srikanth Srinivasan
Schur Polynomials Do Not Have Small Formulas If the Determinant does not.
Comput. Complex.
32 (1) (2023)
Ronen Shaltiel
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
Comput. Complex.
32 (1) (2023)
Michael Kaminski
,
Igor E. Shparlinski
,
Michel Waldschmidt
On sets of linear forms of maximal complexity.
Comput. Complex.
32 (1) (2023)
Rishabh Batra
,
Nitin Saxena
,
Devansh Shringi
Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q.
Comput. Complex.
32 (1) (2023)
Jin-Yi Cai
,
Zhiguo Fu
,
Kurt Girstmair
,
Michael Kowalczyk
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory.
Comput. Complex.
32 (1) (2023)
volume 32, number 2, 2023
Oded Goldreich
,
Dana Ron
A Lower Bound on the Complexity of Testing Grained Distributions.
Comput. Complex.
32 (2) (2023)
Ilario Bonacina
,
Nicola Galesi
,
Massimo Lauria
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares.
Comput. Complex.
32 (2) (2023)
Russell Impagliazzo
,
Valentine Kabanets
,
Ilya Volkovich
The Power of Natural Properties as Oracles.
Comput. Complex.
32 (2) (2023)
Olivier Bournez
,
Arnaud Durand
A Characterization of Functions over the Integers Computable in Polynomial Time Using Discrete Ordinary Differential Equations.
Comput. Complex.
32 (2) (2023)
Caroline Mattes
,
Armin Weiß
Parallel algorithms for power circuits and the word problem of the Baumslag group.
Comput. Complex.
32 (2) (2023)
Ashrujit Ghoshal
,
Ilan Komargodski
On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing.
Comput. Complex.
32 (2) (2023)
Magnus Gausdal Find
,
Alexander Golovnev
,
Edward A. Hirsch
,
Alexander S. Kulikov
Improving 3N Circuit Complexity Lower Bounds.
Comput. Complex.
32 (2) (2023)
Pascal Koiran
,
Subhayan Saha
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond.
Comput. Complex.
32 (2) (2023)
volume 31, number 1, 2022
Austin Conner
,
Fulvio Gesmundo
,
Joseph M. Landsberg
,
Emanuele Ventura
Rank and border rank of Kronecker powers of tensors and Strassen's laser method.
Comput. Complex.
31 (1) (2022)
Igor Carboni Oliveira
,
Rahul Santhanam
,
Roei Tell
Expander-Based Cryptography Meets Natural Proofs.
Comput. Complex.
31 (1) (2022)
Andreas Galanis
,
Leslie Ann Goldberg
,
Andrés Herrera-Poyatos
The complexity of approximating the complex-valued Potts model.
Comput. Complex.
31 (1) (2022)
Adrien Poteaux
,
Martin Weimann
A quasi-linear irreducibility test in 핂[[x]][y].
Comput. Complex.
31 (1) (2022)
Paul Görlach
,
Yue Ren
,
Leon Zhang
Computing zero-dimensional tropical varieties via projections.
Comput. Complex.
31 (1) (2022)
Thomas Watson
Amplification with One NP Oracle Query.
Comput. Complex.
31 (1) (2022)
volume 31, number 2, 2022
Dean Doron
,
Amnon Ta-Shma
,
Roei Tell
On Hitting-Set Generators for Polynomials that Vanish Rarely.
Comput. Complex.
31 (2) (2022)
Mrinal Kumar
,
Ben Lee Volk
A Lower Bound on Determinantal Complexity.
Comput. Complex.
31 (2) (2022)
Katrin Casel
,
Philipp Fischbeck
,
Tobias Friedrich
,
Andreas Göbel
,
J. A. Gregor Lagodzinski
Zeros and approximations of Holant polynomials on the complex plane.
Comput. Complex.
31 (2) (2022)
Vishwas Bhargava
,
Sumanta Ghosh
Improved Hitting Set for Orbit of ROABPs.
Comput. Complex.
31 (2) (2022)
Prerona Chatterjee
,
Mrinal Kumar
,
Adrian She
,
Ben Lee Volk
Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.
Comput. Complex.
31 (2) (2022)
Uma Girish
,
Ran Raz
,
Avishay Tal
Quantum versus Randomized Communication Complexity, with Efficient Players.
Comput. Complex.
31 (2) (2022)
Sevag Gharibian
,
Miklos Santha
,
Jamie Sikora
,
Aarthi Sundaram
,
Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2).
Comput. Complex.
31 (2) (2022)
Oded Goldreich
Improved bounds on the AN-complexity of O(1)-linear functions.
Comput. Complex.
31 (2) (2022)
Ishay Haviv
The Complexity of Finding Fair Independent Sets in Cycles.
Comput. Complex.
31 (2) (2022)
Anup Bhattacharya
,
Sourav Chakraborty
,
Arijit Ghosh
,
Gopinath Mishra
,
Manaswi Paraashar
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond.
Comput. Complex.
31 (2) (2022)
Hiroshi Hirai
,
Motoki Ikeda
A cost-scaling algorithm for computing the degree of determinants.
Comput. Complex.
31 (2) (2022)
volume 30, number 1, 2021
Mark Giesbrecht
,
Armin Jamshidpey
,
Éric Schost
Subquadratic-Time Algorithms for Normal Bases.
Comput. Complex.
30 (1) (2021)
Orr Paradise
Correction to: Smooth and Strong PCPs.
Comput. Complex.
30 (1) (2021)
Fedor Part
,
Iddo Tzameret
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli.
Comput. Complex.
30 (1) (2021)
Ronen Shaltiel
,
Jad Silbak
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels.
Comput. Complex.
30 (1) (2021)
Ben Lee Volk
,
Mrinal Kumar
Lower Bounds for Matrix Factorization.
Comput. Complex.
30 (1) (2021)
Susanna F. de Rezende
,
Or Meir
,
Jakob Nordström
,
Robert Robere
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.
Comput. Complex.
30 (1) (2021)
Jacobo Torán
,
Florian Wörz
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space.
Comput. Complex.
30 (1) (2021)
Orr Paradise
Smooth and Strong PCPs.
Comput. Complex.
30 (1) (2021)
Pranav Bisht
,
Nitin Saxena
Blackbox identity testing for sum of special ROABPs and its border class.
Comput. Complex.
30 (1) (2021)
volume 30, number 2, 2021
Tom Gur
,
Yang P. Liu
,
Ron D. Rothblum
An Exponential Separation Between MA and AM Proofs of Proximity.
Comput. Complex.
30 (2) (2021)
Alexander A. Sherstov
The hardest halfspace.
Comput. Complex.
30 (2) (2021)
Dmitry Itsykson
,
Artur Riazanov
,
Danil Sagunov
,
Petr Smirnov
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
30 (2) (2021)
Amit Sinhababu
,
Thomas Thierauf
Factorization of Polynomials Given by Arithmetic Branching Programs.
Comput. Complex.
30 (2) (2021)
Toniann Pitassi
,
Morgan Shirley
,
Thomas Watson
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.
Comput. Complex.
30 (2) (2021)
Nathanaël Fijalkow
,
Guillaume Lagarde
,
Pierre Ohlmann
,
Olivier Serre
Lower Bounds for Arithmetic Circuits via the Hankel Matrix.
Comput. Complex.
30 (2) (2021)
Dmitry Itsykson
,
Artur Riazanov
,
Danil Sagunov
,
Petr Smirnov
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs.
Comput. Complex.
30 (2) (2021)
volume 29, number 2, 2020
Pavel Hrubes
On ε-sensitive monotone computations.
Comput. Complex.
29 (2) (2020)
Nick Fischer
,
Christian Ikenmeyer
The Computational Complexity of Plethysm Coefficients.
Comput. Complex.
29 (2) (2020)
Rohit Gurjar
,
Thomas Thierauf
Linear Matroid Intersection is in Quasi-NC.
Comput. Complex.
29 (2) (2020)