yusuke1997/dblp-id-title huggingface dataset:
A Note on Approximating MAX-BISECTION on Regular Graphs
Lower Bounds for OBDDs and Nisan's pseudorandom generator
Diagonalization in proof complexity
Testing Odd-Cycle-Freeness in Boolean Functions
Simple and efficient pseudorandom generators from Gaussian processes
Better Binary List-Decodable Codes via Multilevel Concatenation
Complexity Issues in Coding Theory
Testing Booleanity and the Uncertainty Principle
Semialgebraic Proofs and Efficient Algorithm Design
Learning versus Pseudorandom Generators in Constant Parallel Time
Probabilistic logarithmic-space algorithms for Laplacian solvers
On provably disjoint NP-pairs
Computability Theory of Closed Timelike Curves
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity
Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Resettable Zero-Knowledge
Lifting: As Easy As 1, 2, 3
New lower bounds for Polynomial Calculus over non-Boolean bases
Communication Complexity of Set-Intersection Problems and Its Applications
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Characterization of ModL using Prime Modulus
Efficient Amplifiers and Bounded Degree Optimization
Pseudorandom Generators for Width-3 Branching Programs
Improved bounds for the randomized decision tree complexity of recursive majority
Tight bounds on The Fourier Spectrum of AC 0
QMA=PP implies that PP contains PH
Linear and Negative Resolution are Weaker than Resolution
A Note on high-rate Locally Testable Codes with sublinear query complexity
Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing
Towards Coding for Maximum Errors in Interactive Communication
Model-Theoretic Characterization of Complexity Classes
Fooling functions of halfspaces under product distributions
New strong direct product results in communication complexity
Settling the query complexity of non-adaptive junta testing
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
An Improved Composition Theorem of a Universal Relation and Most Functions via Effective Restriction
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
On Approximability of Minimum Bisection Problem
New lower bounds for probabilistic degree and AC0 with parity gates
On the complexity of parallel prefix circuits
On Counting $t$-Cliques Mod 2
Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications
Optimal testing of Reed-Muller codes
Minimization of Decision Trees is Hard to Approximate
Approximation Complexity of Nondense Instances of MAX-CUT
Static Data Structure Lower Bounds Imply Rigidity
Pseudorandomness for Permutation Branching Programs Without the Group Theory
A Polynomial Restriction Lemma with Applications
Number of Variables for Graph Identification and the Resolution of GI Formulas
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas
Lower bounds for regular resolution over parities
Perfect Non-Interactive Zero Knowledge for NP
Some Closure Results for Polynomial Factorization and Applications
Monotone projection lower bounds from extended formulation lower bounds
Low Distortion Embedding from Edit to Hamming Distance using Coupling
Concurrent Non-Malleable Witness Indistinguishability and its Applications
Hitting-sets for ROABP and Sum of Set-Multilinear circuits
Probabilistic abstraction for model checking: An approach based on property testing
Approximability and Nonapproximability by Binary Decision Diagrams
Computation of the Lovász Theta Function for Circulant Graphs
On Probabilistic Checking in Perfect Zero Knowledge
Algorithmic Polynomial Freiman-Ruzsa Theorems
Quasipolynomial bounds for the corners theorem
LDPC Codes Achieve List-Decoding Capacity
On the Power of Random Oracles
Capacity Lower Bounds via Productization
Nisan-Wigderson generators in Proof Complexity: New lower bounds
MidBit + , Torus Polynomials and Non-classical Polynomials: Equivalences for ACC Lower Bounds
Approximating Minimum Unsatisfiability of Linear Equations
Kolmogorov Complexity Conditional to Large Integers
Interactive proofs with competing teams of no-signaling provers
On Random Orderings of Variables for Parity OBDDs
Circuit Lower Bounds for Heuristic MA
Sorting Can Exponentially Speed Up Pure Dynamic Programming
Circuit Lower Bounds for Merlin-Arthur Classes
A large lower bound for 1-branching programs
Explicit Time and Space Efficient Encoders Exist Only With Random Access
Closure of VP under taking factors: a short and simple proof
Constructing Hard Functions from Learning Algorithms
Collision-based Testers are Optimal for Uniformity and Closeness
Decoding Balanced Linear Codes With Preprocessing
Information complexity is computable
A Note on Set Cover Inapproximability Independent of Universe Size
The two queries assumption and Arthur-Merlin classes
Tropical proof systems
A discrepancy lower bound for information complexity
Upper Bounds on Communication in terms of Approximate Rank
Combinatorial and algorithmic aspects of hyperbolic polynomials
High rate locally correctable codes via lifting
Small bias requires large formulas
Reciprocal Inputs in Arithmetic and Tropical Circuits
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Algebraic Lower Bounds for Computing on Encrypted Data
Erasures versus Errors in Local Decoding and Property Testing
On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function
Communication complexity of pointer chasing via the fixed-set lemma
On Two-Level Poset Games
On a D-N-optimal acceptor for TAUT
On the Approximability of a Geometric Set Cover Problem
Strong Parallel Repetition for Unique Games on Small Set Expanders
Extractors for Turing-machine sources
Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model
Better Simulation of Exponential Threshold Weights by Polynomial Weights
Alternation Depth of Threshold Decision Lists
A Note on Adaptivity in Testing Properties of Bounded Degree Graphs
The polynomially bounded perfect matching problem is in NC^2
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
Direct Product Theorems for Communication Complexity via Subdistribution Bounds
Range avoidance, Arthur-Merlin, and TFNP
Malt'sev Constraints made Simple
Fourier bounds and pseudorandom generators for product tests
Linear Sketching over 𝔽 2
How to Recover a Secret with $O(n)$ Additions
On Derandomizing Algorithms that Err Extremely Rarely
On a singular value method in quantum communication complexity
Lower Bounds for Circuits of Bounded Negation Width
Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions
Tight Static Lower Bounds for Non-Adaptive Data Structures
Bounds on Pairs of Families with Restricted Intersections
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity
A trade-off between length and width in resolution
Inapproximability of Sparsest Vector in a Real Subspace
Depth d Frege systems are not automatable unless P=NP
Simulation Beats Richness: New Data-Structure Lower Bounds
Resolution over Linear Equations and Multilinear Proofs
Worst case to Average case reductions for polynomials
A combinatorial analysis for the critical clause tree
Transitive-Closure Spanners of the Hypercube and the Hypergrid
Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms
Closure under factorization from a result of Furstenberg
Complete Classi fication of Generalized Santha-Vazirani Sources
Improved Small Set Expansion in High Dimensional Expanders
Interactive proof systems for FARNESS
Binary Codes with Distance Close to Half
Constant-depth circuits vs. monotone circuits
Finding small OBDDs for incompletely specified truth tables is hard
Agreement testing theorems on layered set systems
Small value parallel repetition for general games
Pseudo-Random Functions and Factoring
Algorithms for Arithmetic Circuits
Detecting Monomials with k Distinct Variables
Inaccessible Entropy
On the Computational Power of Randomized Branching Programs
Another proof that BPP subseteq PH (and more)
Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems
Restriction Trees for Sparsity and Applications
A subexponential lower bound for branching programs restricted with regard to some semantic aspects
Approximations by Computationally-Efficient VCG-Based Mechanisms
Tableau vs. Sequent Calculi for Minimal Entailment
Hardness against Linear Branching Programs and More
On Interactivity in Arthur-Merlin Communication and Stream Computation
Symmetric Distributions from Shallow Circuits
Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman
An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas
Improved approximation algorithms for directed Steiner forest
On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields
The zero-error randomized query complexity of the pointer function
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant
Nearly optimal separations between communication (or query) complexity and partitions
Towards an axiomatic system for Kolmogorov complexity
3CNF Properties are Hard to Test
An Approach to characterize the Regular Languages in TC0 with Linear Wires
Instance-by-instance optimal identity testing
Dynamic Fault Diagnosis
Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing
Strong (D)QBF Dependency Schemes via Pure Universal Resolution Paths
On the Complexity of Testing Membership in the Core of min-Cost Spanning Tree Games
Random nondeterministic real functions and Arthur Merlin games
From Information to Exact Communication
Improved List-Decodability of Reed-Solomon Codes via Tree Packings
A Note on the computational hardness of evolutionary stable strategies
Reconstruction of full rank Algebraic Branching Programs
Partial Bi-Immunity and NP-Completeness
Bounded Queries, Approximations and the Boolean Hierarchy
On Graph Complexity
Explicit Exponential Lower Bounds for Exact Hyperplane Covers
Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC
The Optimization Complexity of Constraint Satisfaction Problems
On Uncertainty versus Size in Branching Programs
Black-Box PPP is not Turing-Closed
(Semi)Algebraic Proofs over ±1 Variables
Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
Rigid Matrices From Rectangular PCPs
An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP
Proving Natural Distribution Properties is Harder than Testing Them
Min-Rank Conjecture for Log-Depth Circuits
Homomorphism polynomials complete for VP
Generalised Linial-Nisan Conjecture is False for DNFs
The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
On read- k projections of the determinant
Depth-First Search in Directed Graphs, Revisited
Non-Malleable Extractors and Codes, with their Many Tampered Extensions
Planar Graph Isomorphism is in Log-space
Welfare Maximization and the Supermodular Degree
A Decision Method for the Rational Sequence Problem
k-connected spanning subgraphs of low degree
Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks
On Cryptography and Distribution Verification, with Applications to Quantum Advantage
Separations of Matroid Freeness Properties
Separating QMA from QCMA with a classical oracle
Notes on Monotone Read-k Circuits
Random Arithmetic Formulas can be Reconstructed Efficiently
The plane test is a local tester for Multiplicity Codes
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm
Parallel Complexity for Matroid Intersection and Matroid Parity Problems
Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
The GGM Construction does NOT yield Correlation Intractable Function Ensembles
Network Coding: Does the Model Need Tuning?
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
Testing (Conditional) Mutual Information
Structure in Communication Complexity and Constant-Cost Complexity Classes
Sunflowers and Quasi-sunflowers from Randomness Extractors
Robust testing of low-dimensional functions
The Log-Rank Conjecture: New Equivalent Formulations
A note on the P versus NP intersected with co-NP question in communication complexity
Monotone Rank and Separations in Computational Complexity
Local List Recovery of High-rate Tensor Codes & Applications
Bounded independence vs. moduli
On Random High Density Subset Sums
Some definitorial suggestions for parameterized proof complexity
A note on a hierarchy theorem for promise-BPTIME
On the Power of Isolation in Planar Structures
Infeasibility of Instance Compression and Succinct PCPs for NP
Lower Bounds from Succinct Hitting Sets
A Characterization of Tree-Like Resolution Size
Graph Ramsey games
Estimating the distance from testable affine-invariant properties
List decoding Reed-Muller codes over small fields
Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths
An average-case depth hierarchy theorem for higher depth
On the Computational Complexity of MaxSAT
In Brute-Force Search of Correlation Bounds for Polynomials
Automating Regular or Ordered Resolution is NP-Hard
Height restricted constant depth LK
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
Neural Networks with Local Receptive Fields and Superlinear VC Dimension
Reducing testing affine spaces to testing linearity
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge
The Ideal Membership Problem and Polynomial Identity Testing
On the Gaussian surface area of spectrahedra
Communication Complexity (for Algorithm Designers)
A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments
Extractors for Affine Sources with Polylogarithmic Entropy
A simple constant-probability RP reduction from NP to Parity P
Constant-time source decoding
Quantum measurements and the Abelian Stabilizer Problem
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma
Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines
New Non-FPT Lower Bounds for Some Arithmetic Formulas
A Tail Bound for Read-k Families of Functions
Algorithms versus Circuit Lower Bounds
Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
On the Uniformity of Distribution of a Certain Pseudo-Random Function
A Proof of Yao's Protocol for Secure Two-Party Computation
Neural Systems as Nonlinear Filters
Computational Complexity of Some Restricted Instances of 3SAT
Deterministically Factoring Sparse Polynomials into Multilinear Factors
Linear-algebraic list decoding for variants of Reed-Solomon codes
Computing the maximum using (min, +) formulas
An Alternative Proof of The Schwartz-Zippel Lemma
The Monotone Theory for the PAC-Model
The sum of d small-bias generators fools polynomials of degree d
On Learning from Ambiguous Information
Efficient Multiparty Protocols via Log-Depth Threshold Formulae
Fractional Linear Matroid Matching is in quasi-NC
Local Decodability of the Burrows-Wheeler Transform
An AC 0 Lower Bound for Random Satisfiable 3-CNF under Standard Random Restrictions
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits
Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies
A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security
Refuting Perfect Matchings in Spectral Expanders is Hard
Streaming bounds from difference ramification
Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin
Approximation Resistant Predicates From Pairwise Independence
A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates
Information Distance and Conditional Complexities
Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions
Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability
Greedy can also beat pure dynamic programming
Towards Optimal Lower Bounds For Clique and Chromatic Number
The Complexity of Agreement
Recovering polynomials over finite fields from noisy character values
1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems
Reachability in O(log n) Genus Graphs is in Unambiguous
Information lower bounds via self-reducibility
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
Reducibility Among Equilibrium Problems
Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems
Dense Testers: Almost Linear Time and Locally Explicit Constructions
A note on Efremenko's Locally Decodable Codes
Explicit two-source extractors for near-logarithmic min-entropy
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
Local list-decoding and testing of random linear codes from high-error
A Note on Read-k Times Branching Programs
Composition of semi-LTCs by two-wise Tensor Products
Separation of NP-completeness Notions
Three Theorems regarding Testing Graph Properties
Existence of Simple Extractors
Low-depth arithmetic circuit lower bounds via shifted partials
Subsampling Semidefinite Programs and Max-Cut on the Sphere
On the Hardness of Approximating Label Cover
On epsilon-Biased Generators in NC0
Determinant: Combinatorics, Algorithms, and Complexity
Sums of read-once formulas: How many summands suffice?
Approximate Counting of Matchings in (3,3)-Hypergraphs
An improved lower bound for the randomized decision tree complexity of recursive majority
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems
Approximate degree of AND via Fourier analysis
On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions
Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme
Lower bounds on information complexity via zero-communication protocols and applications
#SAT Algorithms from Shrinkage
A VLSI Circuit Model Accounting For Wire Delay
One-input-face MPCVP is Hard for L, but in LogDCFL
Reducing 3XOR to listing triangles, an exposition
On the complexity of computational problems regarding distributions (a survey)
Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin
Robust Multiplication-based Tests for Reed-Muller Codes
Two-Sided Lossless Expanders in the Unbalanced Setting
Candidate Lasserre Integrality Gap For Unique Games
A Characterization of Constant-Sample Testable Properties
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations
The Complexity of Constructing Pseudorandom Generators from Hard Functions
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
Launching Identity Testing into (Bounded) Space
Multilinear-NC 1 != Multilinear-NC 2
Fractional certificates for bounded functions
Counting the Number of Perfect Matchings in K 5 -free Graphs
Algorithms for Counting 2-SAT Solutions and Colorings with Applications
Parallel repetition via fortification: analytic view and the quantum case
Inclusion-Exclusion Based Algorithms for Graph Colouring
Counting t -cliques: Worst-case to average-case reductions and Direct interactive proof systems
Communication Complexity of Correlated Equilibrium in Two-Player Games
On correlation bounds against polynomials
Reachability in K 3,3 -free Graphs and K 5 -free Graphs is in Unambiguous Log-Space
On Barnette's conjecture
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs
Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?
Dictatorship is the Most Informative Balanced Function at the Extremes
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)
Verifying whether One-Tape Turing Machines Run in Linear Time
Proof Systems that Take Advice
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2 log n Ω(1) Colors
Random Shortening of Linear Codes and Application
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Neural Nets with Superlinear VC-Dimension
Promise Problems Meet Pseudodeterminism
A note on semantic cutting planes
Symmetry-assisted adversaries for quantum state generation
Polynomial decompositions in polynomial time
Settling the Complexity of 2-Player Nash-Equilibrium
Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits
Multi-pseudodeterministic algorithms
Border Complexity of Symbolic Determinant under Rank One Restriction
When does a dynamic programming formulation guarantee the existence of an FPTAS?
Parallel complexity of integer coprimality
Quantum and Stochastic Programs of Bounded Width
A Generalized Turan Problem and its Applications
The Sign-Rank of AC^0
Quantum Algorithms in a Superposition of Spacetimes
On the Structure of Cubic and Quartic Polynomials
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions
A security analysis of Probabilistically Checkable Proofs
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem
$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors
Sampling Lower Bounds via Information Theory
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-in
Improved Pseudorandom Generators for AC 0 Circuits
Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games
Neural Circuits for Pattern Recognition with Small Total Wire Length
Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps : -)
On the Rational Degree of Boolean Functions and Applications
A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques
Worst-case to average case reductions for the distance to a code
Simulating Access to Hidden Information while Learning
One-way communication complexity and non-adaptive decision trees
Sign rank, VC dimension and spectral gaps
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption
Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata
Derandomizing Chernoff Bound with Union Bound with an Application to k -wise Independent Sets
Teaching and compressing for low VC-dimension
Shared Randomness and Quantum Communication in the Multi-Party Model
One Property of Cross-Intersecting Families
On the Rectangle Method in proofs of Robustness of Tensor Products