yusuke1997/dblp-id-title huggingface dataset:
On Estimating the Average Degree of a Graph
Deterministic Identity Testing of Read-Once Algebraic Branching Programs
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)
Relative to P, APP and promise-BPP are the same
Random 3CNF formulas elude the Lovasz theta function
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond
On Perfect Completeness for QMA
Black-Box Concurrent Zero-Knowledge Requires ~Omega(log n) Rounds
Limitations of Incremental Dynamic Programs
Looking for an Analogue of Rice's Theorem in Complexity Theory
Tri-State Circuits: A Circuit Model that Captures RAM
Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity
Pseudorandomness and Combinatorial Constructions
Deep Neural Networks: The Missing Complexity Parameter
Heuristic time hierarchies via hierarchies for sampling distributions
Direct product via round-preserving compression
On The Power of Membership Queries in Agnostic Learning
Extractors with Weak Random Seeds
The Computational Complexity of Some Problems of Linear Algebra
An Efficient Deterministic Primality Test
On properties that are non-trivial to test
On Yao's XOR-Lemma
Active classification with comparison queries
The Choice and Agreement Problems of a Random Function
Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities
Approximation Limitations of Tropical Circuits
Simplified inpproximability of hypergraph coloring via t-agreeing families
Reducing Tarski to Unique Tarski (in the Black-box Model)
On Existentially First-Order Definable Languages and their Relation to NP
Notes on Levin's Theory of Average-Case Complexity
MAX NP-Completeness Made Easy
Zero Knowledge and Soundness are Symmetric
Inapproximability results for bounded variants of optimization problems
Supermodels and Closed Sets
Near Quadratic Matrix Multiplication Modulo Composites
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree
Analyzing Linear Mergers
Circuit complexity, proof complexity, and polynomial identity testing
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
A Combinatorial Geometric Approach to Linear Image Matching
Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity
Efficient Algorithms for Online Game Playing and Universal Portfolio Management
Towards EXPTIME One Way Functions Bloom Filters, Succinct Graphs & Self Masking
Condensing against Online Adversaries
Formulas are exponentially stronger than monotone circuits in non-commutative setting
On Proximity Gaps for Reed-Solomon Codes
Algorithms for group isomorphism via group extensions and cohomology
Strongly Exponential Lower Bounds for Monotone Computation
Ruling Out Short Proofs of Unprovable Sentences is Hard
An Algorithmic Characterization of Multi-Dimensional Mechanisms
Weights at the Bottom Matter When the Top is Heavy
A short note on (distribution) testing lower bounds via polynomials
Towards an algebraic natural proofs barrier via polynomial identity testing
Parallel Construction of Minimum Redundancy Length-Limited Codes
IPS-like Proof Systems Based on Binary Decision Diagrams
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization
Algebraic Hardness versus Randomness in Low Characteristic
Affine extractors and AC0-Parity
Superredundancy: A tool for Boolean formula minimization complexity analysis
A Characterization of Approximation Resistance
How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments
Optimality of Linear Sketching under Modular Updates
Approximating the entropy of large alphabets
Open Problems in Property Testing of Graphs
An approximation hardness result for bipartite Clique
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
Embedding Hard Learning Problems into Gaussian Space
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Testing Graphs in Vertex-Distribution-Free Models
Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor
Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors
The Independence of the modulo p Counting Principles
Arithmetic Versions of Constant Depth Circuit Complexity Classes
Local decoding and testing of polynomials over grids
Linear Upper Bounds for Random Walk on Small Density Random 3CNFs
Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs
A Linear-Optical Proof that the Permanent is #P-Hard
Expander Construction in VNC 1
Doubly Sub-linear Interactive Proofs of Proximity
Combinatorial Optimization Algorithms via Polymorphisms
Hierarchies Against Sublinear Advice
New Lower Bounds for General Locally Decodable Codes
Polynomial time algorithms to approximate mixed volumes within a simply exponential factor
The median problems for breakpoints are NP-complete
Bounds for the Query Complexity of Approximate Equilibria
On the degree of polynomials computing square roots mod p
Computability and Complexity in Self-Assembly
Circuit size lower bounds and #SAT upper bounds through a general framework
Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size
On Multi-Point Local Decoding of Reed-Muller Codes
Testing Computability by Width-Two OBDDs
Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits
Extractor-Based Time-Space Lower Bounds for Learning
Building Injective Trapdoor Functions From Oblivious Transfer
Security of Polynomial Transformations of the Diffie--Hellma
Modular composition & polynomial GCD in the border of small, shallow circuits
2 (\log N) 1/4-o(1) Hardness for Hypergraph Coloring
On Tseitin formulas, read-once branching programs and treewidth
The Isomorphismproblem for One-Time-Only Branching Programs
Aaronson-Ambainis Conjecture Is True For Random Restrictions
Arithmetic Circuit Size, Identity Testing, and Finite Automata
Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist
Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization
A Composition Theorem via Conflict Complexity
A Compression Algorithm for AC 0 [⊕] circuits using Certifying Polynomials
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions
Green's Theorem and Isolation in Planar Graphs
Hausdorff Dimension and Oracle Constructions
Obfuscation using Tensor Products
Efficiently Batching Unambiguous Interactive Proofs
Parameterized Bounded-Depth Frege is Not Optimal
Uniform, Integral and Feasible Proofs for the Determinant Identities
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games
Near log-convexity of measured heat in (discrete) time and consequences
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation
Pseudorandom Generators for Low-Sensitivity Functions
Exact constructive dimension
A Note on Subspace Evasive Sets
Average-Case Fine-Grained Hardness
Metamathematics of Resolution Lower Bounds: A TFNP Perspective
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity
On the Hardness of 4-coloring a 3-colorable Graph
Oblivious RAMs without Cryptographic Assumptions
Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.
Noisy population recovery in polynomial time
On Nondeterminism versus Randomness for Read-Once Branching Programs
On Monotonicity Testing and Boolean Isoperimetric type Theorems
Clique Problem, Cutting Plane Proofs, and Communication Complexity
Time-Space Tradeoffs for BPL via Catalytic Computation
Towards ACC Lower Bounds using Torus Polynomials
A Note on Yekhanin's Locally Decodable Codes
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems
Interpolation by a Game
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness
Relating existing powerful proof systems for QBF
On polynomial time approximation schemes and approximation preserving reductions
Fourier growth of structured 𝔽 2 -polynomials and applications
Predictive complexity and information
Are all distributions easy?
Algorithmic Minimal Sufficient Statistics: a New Definition
Approximate polymorphisms of predicates
Robust Satisfiability of Constraint Satisfaction Problems
SAT-based Circuit Local Improvement
Branching program, commutator, and icosahedron, part I
Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Average-Case Lower Bounds for Formula Size
Testing equivalence to design polynomials
Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
Bounds on the Kolmogorov complexity function for infinite words
A remark on one-wayness versus pseudorandomness
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
On Approximability of Satisfiable k-CSPs: VI
Time Hierarchies: A Survey
Optimal heuristic algorithms for the image of an injective function
STRIP EXCHANGING IS HARD
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable
A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs
On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions
Multilinear Algebraic Branching Programs and the Min-Partition Rank Method
Security of 2 t -Root Identification and Signatures
Succinct Permanent is NEXP-hard with Many Hard Instances
Universal Quantum Circuits
Bravely, Moderately: A Common Theme in Four Recent Results
3-Coloring in time O(1.3446 n ): A no-MIS Algorithm
Tree PCPs
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
A ZPP^NP[1] Lifting Theorem
Recent advances on the log-rank conjecture in communication complexity
On the Subgroup Distance Problem
Short Proofs are Narrow - Resolution made Simple
A Note on Traversing Skew Merkle Trees
The Bipartite Formula Complexity of Inner-Product is Quadratic
Randomized query composition and product distributions
Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions
Collapsing Catalytic Classes
Sampling lower bounds: boolean average-case and permutations
Quantum Circuits: Fanout, Parity, and Counting
On the Degree of Univariate Polynomials Over the Integers
Lower Bounds for Alternating Online Space Complexity
On top fan-in vs formal degree for depth-3 arithmetic circuits
On the Power of Randomized Ordered Branching Programs
On the Complexity of Rank and Rigidity
Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions
On the Locality of Codeword Symbols
The Optimality of Correlated Sampling
On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out
Moment-Matching Polynomials
Quantum deduction rules
Derandomization of PPSZ for Unique-k-SAT
Approximation Hardness for Small Occurrence Instances of NP-Hard Problem
New connections between derandomization, worst-case complexity and average-case complexity
An exposition of recent list-size bounds of FRS Codes
Information in propositional proofs and algorithmic proof search
Algorithms for SAT and Upper Bounds on Their Complexity
Exponential Lower Bounds Against Sums of ROABPs
Finer separations between shallow arithmetic circuits
Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
Agnostic Learning of Monomials by Halfspaces is Hard
Approximation from linear spaces and applications to complexity
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials
On the Fine-grained Complexity of Least Weight Subsequence in Graphs
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity
Approximate degree lower bounds for oracle identification problems
Nisan-Wigderson generators in proof systems with forms of interpolation
Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
The complexity of matrix rank and feasible systems of linear equations
On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König
Hardness amplification for errorless heuristics
Conditional Disclosure of Secrets and d-Uniform Secret Sharing with Constant Information Rate
Complexity of approximating CSP with Balance / Hard Constraints
A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem
Oblivious Classes Revisited: Lower Bounds and Hierarchies
Sliding Windows With Limited Storage
Pointer chasing via triangular discrimination
On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity
Free Bits, PCP and Non-Approximability - Towards Tight Results
Efficient Communication Establishment in Extremely Unreliable Large Networks
On the Efficiency of Non-Uniform PCPP Verifiers
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
A Space Hierarchy for k-DNF Resolution
Lower bounds for constant query affine-invariant LCCs and LTCs
Collaborative Discovery: A study of Guru-follower dynamics
Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Randomly coloring constant degree graphs
Locally Testable Codes and Cayley Graphs
On teaching the approximation method for circuit lower bounds
On Some Tighter Inapproximability Results, Further Improvements
Scaled Dimension of Individual Strings
Random low degree polynomials are hard to approximate
New Lower Bounds against Homogeneous Non-Commutative Circuits
On the nature of the Theory of Computation (ToC)
One-sided error communication complexity of Gap Hamming Distance
General systems of linear forms: equidistribution and true complexity
On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions
Unprovability of strong complexity lower bounds in bounded arithmetic
Deterministic Depth-4 PIT and Normalization
Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games
Symmetric Polynomials over Z m and Simultaneous Communication Protocols
Tracking the best disjunction
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models
Uniform Circuits, Lower Bounds, and QBF Algorithms
How much commutativity is needed to prove polynomial identities?
Hardness and Approximability in Multi-Objective Optimization
Finding forbidden minors in sublinear time: a n 1/2+o(1) -query one-sided tester for minor closed properties on bounded degree graphs
Complexity of Inverting the Euler Function
Approximating and Testing k -Histogram Distributions in Sub-linear time
BDD-based Cryptanalysis of Keystream Generators
Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
Proof vs. Truth in Computational Complexity
The Direct Sum of Universal Relations
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
Garbled Circuits as Randomized Encodings of Functions: a Primer
Parity helps to compute Majority
Relations between monotone complexity measures based on decision tree complexity
A nonlinear bound on the number of wires in bounded depth circuits
Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties
Improved Approximations for General Minimum Cost Scheduling
Gap MCSP is not (Levin) NP-complete in Obfustopia
Paris-Harrington tautologies
How powerful are the DDH hard groups?
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games
Linear codes cannot approximate the network capacity within any constant factor
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes
On k-term DNF with largest number of prime implicants
The Isomorphism Problem for k-Trees is Complete for Logspace
On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction
Random formulas, monotone circuits, and interpolation
An Invariance Principle for Polytopes
Circuit Lower Bounds in Bounded Arithmetics
Near optimality of the priority sampling procedure
Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends
Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I
Quantum Implications of Huang's Sensitivity Theorem
Hitting Sets For Regular Branching Programs
Functional lower bounds for restricted arithmetic circuits of depth four
BPP has effective dimension at most 1/2 unless BPP=EXP
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility
Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in
Low-error two-source extractors for polynomial min-entropy
Entropy of weight distributions of small-bias spaces and pseudobinomiality
Lower bounds over Boolean inputs for deep neural networks with ReLU gates
Hardness of Low Congestion Routing in Directed Graphs
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
Recognizing Frozen Variables in Constraint Satisfaction Problems
On Pseudorandomness with respect to Deterministic Observers
From RAM to SAT
Property Testing and its connection to Learning and Approximation
The coin problem for product tests
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function
Boolean function analysis on high-dimensional expanders
Factors of Sparse Polynomials are Sparse
Incremental versus Non-Incremental Dynamic Programming
Searching constant width mazes captures the AC 0 hierarchy
Algorithmic Meta-Theorems
Structure vs Hardness through the Obfuscation Lens
On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games
Dimension Extractors
Secure Computation with Information Leaking to an Adversary
Dependency schemes in CDCL-based QBF solving: a proof-theoretic study
Relationless completeness and separations
Soft decoding, dual BCH codes, and better list-decodable eps-biased codes
Counting paths in VPA is complete for #NC 1
3-SAT in RTIME(O(1.32793 n )) - Improving Randomized Local Search by Initializing Strings of 3-Clauses
Super-critical Trade-offs in Resolution over Parities Via Lifting
On Embeddings of ℓ 1 k from Locally Decodable Codes
Strategy-Stealing is Non-Constructive
A separation of PLS from PPP
Parity Decision Tree Complexity is Greater Than Granularity
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs
Algebraic dependencies and PSPACE algorithms in approximative complexity
Trading information complexity for error
On the Width of Semi-Algebraic Proofs and Algorithms
Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols
On the degree of symmetric functions on the Boolean cube
Coherence in Property Testing: Quantum-Classical Collapses and Separations
Storage Enforcement with Kolmogorov Complexity and List Decoding
Dimension-free Bounds and Structural Results in Communication Complexity
A log-space algorithm for reachability in planar DAGs with few sources
Automating Tree-Like Resolution in Time n o(log n) Is ETH-Hard
Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$
A Computational Theory of Awareness and Decision Making
Lower Bounds for Testing Properties of Functions on Hypergrid Domains
Pebble Games and Algebraic Proof Systems Meet Again
Approximating Schedules for Dynamic Graphs Efficiently
Reconstruction of Depth-$4$ Multilinear Circuits
Bounding laconic proof systems by solving CSPs in parallel
Bipartite Matching is in Catalytic Logspace
Does Prior Knowledge Help Detect Collisions?
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters
Randomized Polynomial Time Identity Testing for Noncommutative Circuits
A strong law of computationally weak subsets
Efficiently finding small representations for LTFs
Memorization and Association on a Realistic Neural Model
Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP
Structure of protocols for XOR functions
Approximating Dense Cases of Covering Problems
Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems
Uniform Generation of NP-witnesses using an NP-oracle
A Note on Zero-Knowledge for NP and One-Way Functions
On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds
In a World of P=BPP
Composition of low-error 2-query PCPs using decodable PCPs
Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
A Õ(n) Non-Adaptive Tester for Unateness
A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs
On Complexity of Regular (1,+k)-Branching Programs
Testing linear-invariant non-linear properties: A short report
Bounded independence plus noise fools products
Hardness of Computing Nondeterministic Kolmogorov Complexity
Generating Matrix Identities and Proof Complexity Lower Bounds
Some closure features of locally testable affine-invariant properties
Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints
Reduction From Non-Unique Games To Boolean Unique Games
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields
Deterministic clustering with data nets
Tight lower bounds for 2-query LCCs over finite fields
A Survey of Classes of Primitive Recursive Functions
The communication complexity of functions with large outputs
Common information and unique disjointness
Generating Hard Instances of Lattice Problems
Pushdown Automaton with the Ability to Flip its Stack
On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations
Learning circuits with few negations
Criticality of AC0-Formulae
Discrepancy and the power of bottom fan-in in depth-three circuits
Multilinear Complexity is Equivalent to Optimal Tester Size
On Computation with Pulses
Compression of Boolean Functions
Representing Boolean OR function by quadratic polynomials modulo 6
Reducing Randomness via Chinese Remaindering
Lower bounds for non-commutative skew circuits
Lower bounds for 2-query LCCs over large alphabet
Restriction Access
Non-Malleability against Polynomial Tampering
Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae
On Approximability of Satisfiable k -CSPs: I
Finding Lower Bounds for Nondeterministic State Complexity is Hard
Query-Efficient Locally Decodable Codes
Robust sensitivity
Short PCPs with projection queries
Topology matters in communication
DPLL with Caching: A new algorithm for #SAT and Bayesian Inference
Extractors and condensers from univariate polynomials
Irregular Assignments of the Forest of Paths
NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth
Reductions Between Expansion Problems