Localizability of the approximation method

2024-9-5

Determinants vs. Algebraic Branching Programs

2024-8-31

Variety Evasive Subspace Families

2024-7-16

Combinatorial refinement on circulant graphs

2024-7-15

The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability

2024-7-3

Streaming approximation resistance of every ordering CSP

2024-5-29

Algebraic Global Gadgetry for Surjective Constraint Satisfaction

2024-5-29

Limits of Preprocessing

2024-5-23

KRW Composition Theorems via Lifting

2024-4-29

Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\text{VP} \neq \text{VNP}$$

2024-4-16

On Blocky Ranks Of Matrices

2024-3-6

Approximating the chromatic polynomial is as hard as computing it exactly

2024-1-18

Improving $$3N$$ Circuit Complexity Lower Bounds

2023-12-1

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

2023-11-12

A Lower Bound on the Complexity of Testing Grained Distributions

2023-10-26

On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing

2023-9-13

Parallel algorithms for power circuits and the word problem of the Baumslag group

2023-9-13

Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond

2023-8-3

A Characterization of Functions over the Integers Computable in Polynomial Time Using Discrete Ordinary Differential Equations

2023-7-12

The Power of Natural Properties as Oracles

2023-7-6

Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

2023-5-23

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

2023-5-17

Schur Polynomials Do Not Have Small Formulas If the Determinant does not

2023-5-13

Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q

2023-4-6

On sets of linear forms of maximal complexity

2022-11-29

Quantum versus Randomized Communication Complexity, with Efficient Players

2022-10-28

On Hitting-Set Generators for Polynomials that Vanish Rarely

2022-10-22

Improved Hitting Set for Orbit of ROABPs

2022-10-12

The Complexity of Finding Fair Independent Sets in Cycles

2022-10-11

Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

2022-9-20

A Lower Bound on Determinantal Complexity

2022-9-19

Zeros and approximations of Holant polynomials on the complex plane

2022-7-27

A cost-scaling algorithm for computing the degree of determinants

2022-7-23

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

2022-7-5

Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

2022-7-5

Improved bounds on the AN-complexity of $$O(1)$$-linear functions

2022-6-23

A quasi-linear irreducibility test in $$\mathbb{K}[[x]][y]$$

2022-6-1

Computing zero-dimensional tropical varieties via projections

2022-5-20

Expander-Based Cryptography Meets Natural Proofs

2022-3-16

Amplification with One NP Oracle Query

2022-2-5

The complexity of approximating the complex-valued Potts model

2022-2-3

Rank and border rank of Kronecker powers of tensors and Strassen's laser method

2021-12-18

Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

2021-11-17

Factorization of Polynomials Given by Arithmetic Branching Programs

2021-10-15

Lower Bounds for Arithmetic Circuits via the Hankel Matrix

2021-10-8

Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

2021-8-27

An Exponential Separation Between MA and AM Proofs of Proximity

2021-8-18

The hardest halfspace

2021-8-3

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

2021-7-2

Correction to: Smooth and Strong PCPs

2021-6-1