yusuke1997/dblp-id-title huggingface dataset:
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace
k -Subgraph Isomorphism on AC 0 Circuits
Matrix rigidity of random Toeplitz matrices
On Rigid Matrices and U-Polynomials
Fourier Analysis for Probabilistic Communication Complexity
Communication vs. Computation
Optimality of size-width tradeoffs for resolution
A tight lower bound for restricted pir protocols
Randomization and the Computational Power of Analytic and Algebraic Decision Trees
Limits on Alternation Trading Proofs for Time-Space Lower Bounds
Rank and border rank of Kronecker powers of tensors and Strassen's laser method
Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits
The Privacy of Dense Symmetric Functions
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
Reduced Kronecker Coefficients and Counter-Examples to Mulmuley's Strong Saturation Conjecture SH
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword
Factors of low individual degree polynomials
Two oracles that force a big crunch
Pseudo-Deterministic Query Complexity of Search Problems
Modular Composition Modulo Triangular Sets and Applications
Space-Efficient Recognition of Sparse Self-Reducible Languages
Localizability of the approximation method
Efficient and Optimal Exponentiation in Finite Fields
Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm
The Electrical Resistance of a Graph Captures its Commute and Cover Times
Randomness-Efficient Sampling within NC 1
A Characterization of Functions over the Integers Computable in Polynomial Time Using Discrete Ordinary Differential Equations
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation
Derandomizing Logspace With a Small Shared Hard Drive
Length 3 Edge-Disjoint Paths Is NP-Hard
Complexity and Approximability of the Cover Polynomial
Satisfiability, Branch-Width and Tseitin tautologies
On a Theorem of Razborov
The Relative Power of Logspace and Polynomial Time Reductions
The complexity of tensor calculus
On a Hierarchy of Spectral Isomorphism Invariants
Quantum Arthur-Merlin games
Extractors And Rank Extractors For Polynomial Sources
The Value of Help Bits in Randomized and Average-Case Complexity
A quasi-linear irreducibility test in 핂[[x]][y]
On the complexity of approximating tsp with neighborhoods and related problems
Circuits Constructed with Mod_q Gates Cannot Compute "And" in Sublinear Size
On the connection between interval size functions and path counting
The complexity of semilinear problems in succinct representation
Inductive Time-Space Lower Bounds for Sat and Related Problems
Using Elimination Theory to Construct Rigid Matrices
A Note on Logspace Optimization
A New Recursion-Theoretic Characterization of the Polytime Functions
Tensor surgery and tensor rank
Two Tapes Versus One for Off-Line Turing Machines
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
Parameterized complexity of constraint satisfaction problems
On Lower Bounds for Read-K-Times Branching Programs
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
On vanishing of Kronecker coefficients
The average sensitivity of square-freeness
A cost-scaling algorithm for computing the degree of determinants
Schur Polynomials Do Not Have Small Formulas If the Determinant does not
On sunflowers and matrix multiplication
Complexity Theoretic Hardness Results for Query Learning
Constructive non-commutative rank computation is in deterministic polynomial time
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
Randomness Complexity of Private Computation
A compendium of problems complete for symmetric logarithmic space
On Closure Properties of GapP
A quadratic lower bound for homogeneous algebraic branching programs
The BNS-Chung criterion for multi-party communication complexity
Quantum Query Complexity of Almost All Functions with Fixed On-set Size
Query-to-Communication Lifting for P NP
Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword
The Strength of Multilinear Proofs
Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword
Relativized Isomorphisms of NP-Complete Sets
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP
The Computational Complexity of Plethysm Coefficients
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
Straight-line programs and torsion points on elliptic curves
Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers
On the complexity of vertex-disjoint length-restricted path problems
Complexity lower bounds for randomized computation trees over zero characteristic fields
Space Functions and Space Complexity of the Word Problem in Semigroups
Complexity of some arithmetic problems for binary polynomials
Primality Testing with Fewer Random Bits
A counterexample to the chain rule for conditional HILL entropy
Factorization of Polynomials Given by Arithmetic Branching Programs
On approximability of Satisfiable k-CSPs: I
Inapproximability of the Tutte polynomial of a planar graph
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Generic Complexity of Finitely Presented Monoids and Semigroups
Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
Basis Collapse in Holographic Algorithms
Testing list H-homomorphisms
Block-symmetric polynomials correlate with parity better than symmetric
Random resolution refutations
Simulation Theorems via Pseudo-random Properties
Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword
On Derandomized Composition of Boolean Functions
Special Issue on Circuit Complexity: Foreword
Space Hierarchy Results for Randomized and other Semantic Models
Computing Frobenius Maps and Factoring Polynomials
The Complexity of the Max Word Problem and the Power of One-Way Interactive Proof Systems
A Note on Rabin's Width of a Complete Proof
Query-Efficient Locally Decodable Codes of Subexponential Length
Vanishing of Littlewood-Richardson polynomials is in P
On sets of linear forms of maximal complexity
On The Randomness Complexity of Property Testing
Towards lower bounds on locally testable codes via density arguments
Valiant's model and the cost of computing integers
Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword
Robust Algorithms For Generalized Pham Systems
On Space and Depth in Resolution
Collecting Coupons on Trees, and the Cover Time of Random Walks
Finding Maximal Orders in Semisimple Algebras Over Q
Computing the euler-poincaré characteristics of sign conditions
A Theory of Strict P-Completeness
DNF sparsification and a faster deterministic counting algorithm
Improved bounds on the AN-complexity of O(1)-linear functions
The Alternation Hierarchy for Sublogarithmic Space is Infinite
Probabilistic Communication Complexity Over The Reals
Complexity of Positivstellensatz proofs for the knapsack
Fast Exponentiation Using the Truncation Operation
Nullstellensätze for Zero-Dimensional Gröbner Bases
List-Decoding Barnes-Wall Lattices
Counting Curves and Their Projections
Computing zero-dimensional tropical varieties via projections
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality
The correct exponent for the Gotsman-Linial Conjecture
Towards proving strong direct product theorems
A separation of syntactic and nonsyntactic (1, +k)-branching programs
Correction to: Smooth and Strong PCPs
Well-Known Bound for the VC-Dimension Made Easy
Counting Connected Components of a Semialgebraic Set in Subexponential Time
Homogeneous Formulas and Symmetric Polynomials
A quantifier elimination for the theory of p -adic numbers
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
Interactive protocols over the reals
Lower Bounds on Arithmetic Circuits Via Partial Derivatives
How can a Complex Square Root be Computed in an Optimal Way
Rank-one quantum games
Circuits on cylinders
Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas
A Lower Bound on the Complexity of Testing Grained Distributions
Invariance Properties of Rams and Linear Time
Pseudorandom functions in TC 0 and cryptographic limitations to proving lower bounds
Lower bounds for the multiplicative complexity of matrix multiplication
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
Relativizing small complexity classes and their theories
Which bases admit non-trivial shrinkage of formulae?
Interactive proofs and a Shamir-like result for real number computations
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
Correction to: Query-to-Communication Lifting for P NP
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time
Holographic reduction, interpolation and hardness
Barriers for rectangular matrix multiplication
Lower Bounds for k-DNF Resolution on Random 3-CNFs
Polynomial-Time Compression
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
Majority Gates VS. General Weighted Threshold Gates
Hard examples for the bounded depth Frege proof system
On-line Learning of Linear Functions
Small PCPs with low query complexity
On the Oracle Complexity of Factoring Integers
PPSZ for General k-SAT and CSP - Making Hertli's Analysis Simpler and 3-SAT Faster
Representing Boolean Functions as Polynomials Modulo Composite Numbers
Selection Problems via M-Ary Queries
Derandomized Parallel Repetition via Structured PCPs
Space-Efficient Counting in Graphs on Surfaces
The complexity of the covering radius problem
Lower Bounds for the Non-Linear Complexity of Algebraic Computation Trees with Integer Inputs
Two-closures of supersolvable permutation groups in polynomial time
The Sum of D Small-Bias Generators Fools Polynomials of Degree D
Cryptographic Hardness of Random Local Functions - Survey
Random Cnf's are Hard for the Polynomial Calculus
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
Fast computation of the Smith form of a sparse integer matrix
Affine extractors over large fields with exponential error
On the complexity of computing determinants
Correction: Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms
Deterministic polynomial identity testing in non-commutative models
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers
Short lists for shortest descriptions in short time
A Deterministic Test for Permutation Polynomials
Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword
Finding Irreducible Components of Some Real Transcendental Varieties
Existence and Efficient Construction of Fast Fourier Transforms on Supersolvable Groups
Circuits and Multi-Party Protocols
Constructions of Low-degree and Error-Correcting epsilon-Biased Generators
Function-Algebraic Characterizations of Log and Polylog Parallel Time
A Generic Time Hierarchy with One Bit of Advice
On Being Incoherent Without Being Very Hard
Composition of semi-LTCs by two-wise tensor products
Special issue from RANDOM'09: Editors' Foreword
On the Complexity of Planar Boolean Circuits
On the security of Goldreich's one-way function
Algorithmic Properties of Maximal Orders in Simple Algebras over Q
On the power of algebraic branching programs of width two
Improved Low-Density Subset Sum Algorithms
The Black-Box Query Complexity of Polynomial Summation
Non-commutative Edmonds' problem and matrix semi-invariants
Limits on the Hardness of Lattice Problems in l p Norms
2-Transitivity is Insufficient for Local Testability
Approximating the chromatic polynomial is as hard as computing it exactly
Mining Circuit Lower Bound Proofs for Meta-Algorithms
Undirected s-t Connectivity in Polynomial Time and Sublinear Space
Hard submatrices for non-negative rank and communication complexity
Deterministic polynomial identity tests for multilinear bounded-read formulae
Lower bounds for the bilinear complexity of associative algebras
Communication Complexity Under Product and Nonproduct Distributions
Graph Isomorphism, Color Refinement, and Compactness
Quantum commitments from complexity assumptions
Comparing the strength of query types in property testing: The case of k-colorability
Special Issue "Conference on Computational Complexity 2011" Guest Editor's Foreword
A characterization of span program size and improved lower bounds for monotone span programs
(Working Group Noaï Fitchas) Algorithmic Aspects of Suslin's Proof of Serre's Conjecture
On Uniformity and Circuit Lower Bounds
Random low-degree polynomials are hard to approximate
Improved direct product theorems for randomized query complexity
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
An Average Complexity Measure that Yields Tight Hierarchies
The Quantifier Structure of Sentences That Characterize Nondeterministic Time Complexity
Alternation in interaction
Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
The complexity of constructing pseudorandom generators from hard functions
The "log rank" conjecture for modular communication complexity
Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems
Every 2-csp Allows Nontrivial Approximation
On the Structure of Boolean Functions with Small Spectral Norm
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness
A complexity gap for tree resolution
Parallel Approximation of Min-Max Problems
Reflections on "Representations of Sets of Boolean Functions by Commutative Rings" by Roman Smolensky
Complexity of Tropical and Min-plus Linear Prevarieties
Pseudorandom generators for combinatorial checkerboards
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
The Complexity of Approximating complex-valued Ising and Tutte partition functions
Tradeoff lower lounds for stack machines
When do Extra Majority Gates Help? Polylog( N ) Majority Gates Are Equivalent to One
On the size of randomized OBDDs and read-once branching programs for k-stable functions
The Complexity of Boolean Functions in Different Characteristics
Language compression and pseudorandom generators
On the complexity of approximating k -set packing
Function algebraic characterizations of the polytime functions
Complexity of Hard-Core Set Proofs
Multipartite Quantum Correlation and Communication Complexities
Three Sigma^p_2-Complete Problems in Computational Learning Theory
Quantum Automating TC 0 -Frege Is LWE-Hard
NC¹: The Automata-Theoretic Viewpoint
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic
On Matrix Rigidity and Locally Self-correctable Codes
Asymptotic tensor rank of graph tensors: beyond matrix multiplication
Hardness Amplification via Space-Efficient Direct Products
A thirty Year old conjecture about promise problems
Monadic Logical Definability of Nondeterministic Linear Time
Efficiently Certifying Non-Integer Powers
Polynomial multiplication over finite fields: from quadratic to straight-line complexity
Parallel Pointer Machines
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
A Quantum Characterization Of NP
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions
The hardest halfspace
Some observations on holographic algorithms
An Improved Analysis of Linear Mergers
A Complexity Dichotomy For Hypergraph Partition Functions
Low-degree test with polynomially small error
On interactive proofs with a laconic prover
Efficient Randomized Generation of Optimal Algorithms for Multiplication in Certain Finite Fields
Communication complexity towards lower bounds on circuit depth
On the complexity of computing Kronecker coefficients
On the complexity of simulating space-bounded quantum computations
Information-theoretic approximations of the nonnegative rank
Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword
Interpolation of Shifted-Lacunary Polynomials
Exponential lower bounds for depth three Boolean circuits
Weakly Complete Problems are not Rare
Autoreducibility of NP-Complete Sets under Strong Hypotheses
Random arithmetic formulas can be reconstructed efficiently
Evaluating Spectral Norms for Constant Depth Circuits with Symmetric Gates
Complexity of Ring Morphism Problems
On reducing factorization to the discrete logarithm problem modulo a composite
Combinatorial refinement on circulant graphs
Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
Arithmetization: A New Method in Structural Complexity Theory
Tribute to Roman Smolensky
Balancing Syntactically Multilinear Arithmetic Circuits
On the relation between entropy and the average complexity of trajectories in dynamical systems
Subquadratic-Time Algorithms for Normal Bases
On the complexity of inverting integer and polynomial matrices
Quantum state testing beyond the polarizing regime and quantum triangular discrimination
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting
Parallel algorithms for power circuits and the word problem of the Baumslag group
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions
PI k Mass Production and an Optimal Circuit for the Neciporuk Slice
Pseudorandom Generators and Learning Algorithms for AC^0
The complexity of intersecting finite automata having few final states
Using Amplification to Compute Majority with Small Majority Gates
Is Valiant-Vazirani's isolation probability improvable?
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
Neat function algebraic characterizations of logspace and linspace
Lower bounds for linear locally decodable codes and private information retrieval
Hadamard tensors and lower bounds on multiparty communication complexity
Amplifying circuit lower bounds against polynomial time, with applications
On the Rank of Certain Finite Fields
Parallel Time and Quantifier Prefixes
Derandomized Graph Products
Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword
Correction to: Communication complexity with small advantage
Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes
On the power of unambiguity in log-space
Recursion Schemata for Slowly Growing Depth Circuit Classes
RL <= SC
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Polynomials that Sign Represent Parity and Descartes' Rule of Signs
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity
Quantum versus Randomized Communication Complexity, with Efficient Players
On Coherence, Random-Self-Reducibility, and Self-Correction
On the Efficiency of Effective Nullstellensätze
Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms
An exponential lower bound on the size of algebraic decision trees for Max
Derandomizing Arthur-Merlin games under uniform assumptions
The remote set problem on lattices
Solvability of systems of polynomial congruences modulo a large prime
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
On the Decidability of Sparse Univariate Polynomial Interpolation
Local Expanders
Topological lower bounds for arithmetic networks
The complexity of estimating min-entropy
Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions
Lower bounds for modular counting by circuits with modular gates
All Natural NP-Complete Problems Have Average-Case Complete Versions
Languages to diagonalize against advice classes
Adaptive Versus Nonadaptive Queries to NP and p-Selective Sets
Symmetric Alternation Captures BPP
Special Issue "Conference on Computational Complexity 2013" Guest editor's foreword
The Computational Complexity of Recognizing Permutation Functions
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability
Complexity of Solving Tropical Linear Systems
Easy Lower Bound for a Strange Computational Model
Decompositions of Algebras Over R and C
Connect Four and Graph Decomposition
On the Hardness of Computing the Permanent of Random Matrices
Counting Irreducible Components of Complex Algebraic Varieties
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model
On Defining Integers And Proving Arithmetic Circuit Lower Bounds
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols
Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q
Lower Bounds for Agnostic Learning via Approximate Rank
The complexity of chromatic strength and chromatic edge strength
Interpolation in Valiant's Theory
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
Computing Boolean Functions by Polynomials and Threshold Circuits
An adaptivity hierarchy theorem for property testing
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity
Zeros and approximations of Holant polynomials on the complex plane
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy
Separability and one-way functions
Special Issue In Memory of Misha Alekhnovich. Foreword
Sparse affine-invariant linear codes are locally testable
The complexity of approximating the complex-valued Potts model
Representations of Sets of Boolean Functions by Commutative Rings
Variety Evasive Sets
Quantum computation of zeta functions of curves
2-Local Random Reductions to 3-Valued Functions
Improved Depth Lower Bounds for Small Distance Connectivity
On P versus NP cap co-NP for decision trees and read-once branching programs
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword
The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability
A parallel repetition theorem for entangled projection games
Top-Down Lower Bounds for Depth-Three Circuits
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword
On ε-sensitive monotone computations
Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication
The Gaussian Surface Area and Noise Sensitivity of Degree- d Polynomial Threshold Functions
Linear Matroid Intersection is in Quasi-NC
Non-interactive proofs of proximity
Equivalence of Polynomial Identity Testing and Polynomial Factorization
Depth-3 arithmetic circuits over fields of characteristic zero
Deterministic polynomial-time quantum algorithms for Simon's problem
Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication
Learning algorithms from circuit lower bounds
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size
On semiring complexity of Schur polynomials
On the Structure of Learnability beyond P/poly
Blackbox identity testing for sum of special ROABPs and its border class
The Complexity of Matrix Rank and Feasible Systems of Linear Equations
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword
On Randomized One-Round Communication Complexity
An AC 1-complete model checking problem for intuitionistic logic
Probabilistic Type-2 Operators and "Almost"-Classes
Bounds on Tradeoffs Between Randomness and Communication Complexity