yusuke1997/dblp-id-title huggingface dataset:
A rank lower bound for cutting planes proofs of Ramsey Theorem
Upper Bounds on the Complexity of some Galois Theory Problems
Listings and logics
Proper Learning of k-term DNF Formulas from Satisfying Assignments
Equivalence of polynomial conjectures in additive combinatorics
Locally Computed Baire's Categories on Small Complexity Classes
On Approximate Symmetric Polynomials and Tightness of Homogenization Results
Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank
Nonclassical polynomials as a barrier to polynomial lower bounds
Extractors for Sum of Two Sources
Checking Equality of Matroid Linear Representations and the Cycle Matching Problem
Simplified derandomization of BPP using a hitting set generator
Matching Smolensky's correlation bound with majority
A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
Strong Batching for Non-Interactive Statistical Zero-Knowledge
On the asymptotic complexity of sorting
New correlation bounds for GF(2) polynomials using Gowers uniformity
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs
Unique k-SAT is as Hard as k-SAT
Computing the Maximum Bichromatic Discrepancy, with applications to Computer Graphics and Machine Learning
Constant-Round Zero-Knowledge Proofs of Knowledge
Revisiting a Lower Bound on the Redundancy of Linear Batch Codes
Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
Constant-round interactive proof systems for AC0[2] and NC1
Any Beamsplitter Generates Universal Quantum Linear Optics
The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups
3-NASH is PPAD-Complete
Hardness of Approximately Solving Linear Equations Over Reals
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP
Sampling-based proofs of almost-periodicity results and algorithmic applications
Design Extractors, Non-Malleable Condensers and Privacy Amplification
A Meta-Complexity Characterization of Minimal Quantum Cryptography
Hard satisfiable formulas for splittings by linear combinations
Bounded Pushdown dimension vs Lempel Ziv information density
Every Minor-Closed Property of Sparse Graphs is Testable
3.1n - o(n) Circuit Lower Bounds for Explicit Functions
Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments
High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts
Is the Valiant-Vazirani Isolation Lemma Improvable?
An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists
A refinement of the Meyer-McCreight Union Theorem
On the Complexity of Two-Party Differential Privacy
Locally Testable Non-Malleable Codes
Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors
An Efficient Coding Theorem via Probabilistic Representations and its Applications
Multilinear Formulas and Skepticism of Quantum Computing
Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials
One time-travelling bit is as good as logarithmically many
Reasonable Bounds for Combinatorial Lines of Length Three
Communication Complexity of Equality and Error Correcting Codes
Approximate degree, secret sharing, and concentration phenomena
Property Testing in Bounded Degree Hypergraphs
Testing graphs for colorability properties
Graph partitioning via adaptive spectral techniques
Estimating the unseen: A sublinear-sample canonical estimator of distributions
Balanced Max 2-Sat might not be the hardest
Hard submatrices for non-negative rank and communication complexity }
Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$
On coarse and fine approximate counting of t -cliques
A Sample of Samplers - A Computational Perspective on Sampling (survey)
On the Power of Different Types of Restricted Branching Programs
Inverting a permutation is as hard as unordered search
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)
List Decoding Using the XOR Lemma
Deterministic factorization of constant-depth algebraic circuits in subexponential time
An improved protocol for ExactlyN with more than 3 players
Public vs private coin in bounded-round information
Bipartite Perfect Matching is in quasi-NC
Edge-isoperimetric inequalities and influences
A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games
Lower Bounds for the Computational Power of Networks of Spiking Neurons
Linear Hashing with ℓ ∞ guarantees and two-sided Kakeya bounds
Asymmetric k-center is log * n-hard to Approximate
On the complexity of succinct zero-sum games
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Aggregates with Component Size One Characterize Polynomial Space
The Matching Problem in General Graphs is in Quasi-NC
Fast Approximate Matrix Multiplication by Solving Linear Systems
Unconditional Pseudorandomness against Shallow Quantum Circuits
Classical Physics and the Church-Turing Thesis
A Note on Teaching for VC Classes
Computational Indistinguishability - Algorithms vs. Circuits
Time Hierarchies for Computations with a Bit of Advice
Combinatorial Property Testing (a survey)
The space complexity of cutting planes refutations
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs
Mal'tsev constraints are tractable
Post-Quantum Succinct Arguments
The Orbit problem is in the GapL Hierarchy
One-counter verifiers for decidable languages
Chain Rules for Time-Bounded Kolmogorov Complexity
The computational complexity of Evolutionarily Stable Strategies
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets
Leontief Economies Encode Nonzero Sum Two-Player Games
Strict Polynomial-time in Simulation and Extraction
Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution
Randomization and nondeterminsm are incomparable for ordered read-once branching programs
Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs
A Combinatorial Characterization of smooth LTCs and Applications
From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids
Gambling, Computational Information, and Encryption Security
A Derandomized Sparse Johnson-Lindenstrauss Transform
Beating the random assignment on constraint satisfaction problems of bounded degree
Testing Equality in Communication Graphs
A new characterization of VNP via Colored Determinant
New Protocols for Conditional Disclosure of Secrets (and More)
Computational Complexity in Property Testing
Polar Codes: Speed of polarization and polynomial gap to capacity
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces
Explicit resilient functions matching Ajtai-Linial
Stable basis families and complexity lower bounds
Query Complexity and Error Tolerance of Witness Finding Algorithms
An Invitation to the Promise Constraint Satisfaction Problem
Lower Bounds for Kernelizations
The Relative Complexity of Local Search Heuristics and the Iteration Principle
A lower bound for dynamic approximate membership data structures
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas
Diameter versus Certificate Complexity of Boolean Functions
Pseudo-deterministic Streaming
Packing Edge-Disjoint Triangles in Given Graphs
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion
Towards a Proof of the 2-to-1 Games Conjecture?
Infinitely-Often Universal Languages and Diagonalization
Testers and their Applications
Automating Algebraic Proof Systems is NP-Hard
Using higher-order Fourier analysis over general fields
PSPACE contains almost complete problems
Randomness-Efficient Sampling within NC^1
Extractors for Sumset Sources
A Counterexample to the Generalized Linial-Nisan Conjecture
Languages that are Recognized by Simple Counter Automata are not necessarily Testable
One-way Communication and Non-adaptive Decision Tree
Ideals, Gröbner Bases, and PCPs
Low-Degree Polynomials Extract from Local Sources
Derandomizing Dynamic Programming and Beyond
A Compendium of Problems Complete for Symmetric Logarithmic Space
Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties
Key Agreement from Weak Bit Agreement
Total Variation Distance Estimation Is as Easy as Probabilistic Inference
Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits
Information Theoretically Secure Databases
2-Server PIR with sub-polynomial communication
The Global Power of Additional Queries to p-random Oracles
Trapdoors for Hard Lattices and New Cryptographic Constructions
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets
Extractors for Samplable Distributions from the Two-Source Extractor Recipe
Combinatorial limitations of a strong form of list decoding
Regular Languages in MAJ[>] with three variables
Quantum Log-Approximate-Rank Conjecture is also False
Small-bias is not enough to hit read-once CNF
Machines that can Output Empty Words
A Taxonomy of Enhanced Trapdoor Permutations
Average-Case PAC-Learning from Nisan's Natural Proofs
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
PLS is contained in PLC
Torus polynomials: an algebraic approach to ACC lower bounds
Improveing the alphabet size in high noise, almost optimal rate list decodable codes
Neither Reading Few Bits Twice nor Reading Illegally Helps Much
The Resolution Width Problem is EXPTIME-Complete
The Parallel Repetition Conjecture for Trees is True
Plane vs. Plane Low Degree Test
Improved bounds for perfect sampling of $k$-colorings in graphs
BosonSampling Is Far From Uniform
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs
Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification
A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs
Lower bounds on the Deterministic and Quantum Communication Complexity of HAM n a
Quantum One-Sided Exact Error Algorithms
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1
The intersection of two halfspaces has high threshold degree
Efficient Digital to Analog Encoding
Estimation of Graph Isomorphism Distance in the Query World
The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions
Polynomial equation elimination via Tarski Algebra
Verifying computations without reexecuting them: from theoretical possibility to near-practicality
Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs
On the Optimality of a Class of LP-based Algorithms
Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes
On matrix rigidity and locally self-correctable codes
On a syntactic approximation to logics that capture complexity classes
A multi-prover interactive proof for NEXP sound against entangled provers
An infinitely-often one-way function based on an average-case assumption
Boolean functions with small approximate spectral norm
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation
Parametrizing Above Guaranteed Values: MaxSat and MaxCut
Non-linear Inequalities between Predictive and Kolmogorov Complexity
On the Deduction Theorem and Complete Disjoint NP-Pairs
Probabilistic Proof Systems (A Survey)
Constraint satisfaction: The approximability of minimization problems
Recognizing permutation functions in polynomial time
The Rate of Interactive Codes is Bounded Away from 1
Some limitations of the sum of small-bias distributions
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments
Improved rank bounds for design matrices and a new proof of Kelly's theorem
Combinatorics of Monotone Computations
Decodability of Group Homomorphisms beyond the Johnson Bound
Tight bounds for communication assisted agreement distillation
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Lifting to regular resolution over parities via games
Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility
On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs
Improved Upper Bounds for 3-SAT
Lower Bounds for Linear Decision Lists
Quasirandom groups enjoy interleaved mixing
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
A Meta-Complexity Characterization of Quantum Cryptography
The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials
Hardness of Constant-round Communication Complexity
Total space in resolution
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing
Certifying Polynomials for AC 0 [⊕] circuits, with applications
A Simple Biased Distribution for Dinur's Construction
Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n] d
The Complexity of Estimating Min-Entropy
Constant-error pseudorandomness proofs from hardness require majority
Inherent logic and complexity
New Approximation Algorithms for the Steiner Tree Problems
A Note on Closure Properties of ModL
Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs
Towards Hardness of Envy-Free Pricing
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces
The Non-Hardness of Approximating Circuit Size
The Degree of Threshold Mod 6 and Diophantine Equations
Three XOR-Lemmas - An Exposition
On the complexity of computing minimal unsatisfiable LTL formulas
A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials
Fast Matrix Multiplication: Limitations of the Laser Method
On the Complexity of Trial and Error
A Note on Subgroup Membership Problem for PSL(2,p)
A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications
Product mixing in compact Lie groups
Border complexity via elementary symmetric polynomials
Outcome Indistinguishability
Sublinear quantum algorithms for estimating von Neumann entropy
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise
Better pseudorandom generators from milder pseudorandom restrictions
Boolean Complexity Classes vs. Their Arithmetic Analogs
Matching-Vector Families and LDCs Over Large Modulo
Limits to black-box amplification in QMA
On the Security of Diffie-Hellman Bits
Lower Bounds for non-Boolean Constraint Satisfaction
An Elementary Construction of Constant-Degree Expanders
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere
Optimizing the Layout of a Balanced Tree
Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping
A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem
A simple proof of the Isolation Lemma
Lower bounds for arithmetic circuits via the Hankel matrix
Weak Kernels
Proof verification and the hardness of approximation problems
Deterministic Polynomial Factoring and Association Schemes
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity
Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets
Doubly infinite separation of quantum information and communication
Explicit Maximally Recoverable Codes with Locality
Average-Case Complexity
Pseudorandomness for read-once formulas
Average Time Complexity Classes
From Weak to Strong LP Gaps for all CSPs
Finding Cycles and Trees in Sublinear Time
Tight bounds on the Fourier growth of bounded functions on the hypercube
The complexity of proving that a graph is Ramsey
Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
Most Juntas Saturate the Hardcore Lemma
Pseudorandom generators for CC 0 [p] and the Fourier spectrum of low-degree polynomials over finite fields
Pseudo-Mixing Time of Random Walks
On the Algebraic Complexity of Integer Programming
Selection from Structured Data Sets
Boosting and hard-core set constructions: a simplified approach
Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs
Communication complexity of half-plane membership
Learning Parities with Structured Noise
Constant rate PCPs for circuit-SAT with sublinear query complexity
Towards P $\neq$ NP from Extended Frege Lower Bounds
A better-than-3n lower bound for the circuit complexity of an explicit function
Exponential Separation Between Powers of Regular and General Resolution Over Parities
The Exact Multiplicative Complexity of the Hamming Weight Function
Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution
Non-Malleable Extractors with Logarithmic Seeds
Realizable Paths and the NL vs L Problem
A Survey of Lower Bounds for Satisfiability and Related Problems
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
Oracles and Queries That Are Sufficient for Exact Learning
Some Connections between Bounded Query Classes and Non-Uniform Complexity
Explicit separations between randomized and deterministic Number-on-Forehead communication
A Lower Bound for Randomized Read-k-Times Branching Programs
Lower bounds for designs in symmetric spaces
Uniform Inclusions in Nondeterministic Logspace
Enumerations of the Kolmogorov Function
Vanishing-Error Approximate Degree and QMA Complexity
Variants of the Determinant polynomial and VP-completeness
On the performance of WEAK-HEAPSORT
Understanding Gentzen and Frege systems for QBF
Small Error Versus Unbounded Error Protocols in the NOF Model
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness
On linear-algebraic notions of expansion
Time hierarchies for cryptographic function inversion with advice
Limits on the rate of locally testable affine-invariant codes
On the list recoverability of randomly punctured codes
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry
On hardness of multilinearization, and VNP completeness in characteristics two
Multiparty Communication Complexity of AC^0
A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits
On the Lattice of Clones Below the Polynomial Time Functions
Negations are powerful even in small depth
Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
Some notes on two lower bound methods for communication complexity
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs
2 log 1-έ n Hardness for Closest Vector Problem with Preprocessing
A Zero Knowledge Sumcheck and its Applications
Deconstructing 1-local expanders
Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions
A Short Excursion into Semi-Algebraic Hierarchies
A Linear Space Algorithm for Computing the Hermite Normal Form
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding
Concurrent Zero-Knowledge With Timing, Revisited
Should decisions in QCDCL follow prefix order?
Low-soundness direct-product testers and PCPs from Kaufman-Oppenheim complexes
When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions
Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees
Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy
On the Circuit Complexity of Composite Galois Field Transformations
Pseudorandom bits and lower bounds for randomized Turing machines
Simple doubly-efficient interactive proof systems for locally-characterizable sets
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams
The Structure of In-Place Space-Bounded Computation
The space "just above" BQP
Dimension is compression
A Note on Lower Bounds for Monotone Multilinear Boolean Circuits
Zero-Knowledge twenty years after its invention
Width Hierarchy for k -OBDD of Small Width
Connections Between Unique Games and Multicut
Essentially every unimodular matrix defines an expander
On defining PPT-search problems
Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers
Improved Bounds on the Sign-Rank of AC 0
On the closures of monotone algebraic classes and variants of the determinant
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem
Stronger Cell Probe Lower Bounds via Local PRGs
Overlays and Limited Memory Communication Mode(l)s
Resolution and the binary encoding of combinatorial principles
Graph Isomorphism is Low for ZPP NP and other Lowness results
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition
Metric Construction, Stopping Times and Path Coupling
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions
NP-complete Problems and Physical Reality
Testing Orientation Properties
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
An epsilon-Biased Generator in NC0
Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification
Least span program witness size equals the general adversary lower bound on quantum query complexity
Unprovability of circuit upper bounds in Cook's theory PV
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas
Reducibility Among Fractional Stability Problems
Improved lifting theorems via robust sunflowers
On the Power of Public-key Encryption in Secure Computation
Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs
Fourier Spectrum of Noisy Quantum Algorithms
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
Making the long code shorter, with applications to the Unique Games Conjecture
The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs
A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture
On OBDD-based algorithms and proof systems that dynamically change order of variables
Lifting for Arbitrary Gadgets
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
The Complexity of Geometric Graph Isomorphism
Fooling polynomials using invariant theory
Multiparty Communication Complexity of Disjointness
2048 is (PSPACE) Hard, but Sometimes Easy
Better Complexity Bounds for Cost Register Machines
On Operations of Geometrical Projection and Monotone Extension
Super Strong ETH is true for strong PPSZ
Property Testing on Linked Lists
Linear Space Streaming Lower Bounds for Approximating CSPs
Extracting All the Randomness from a Weakly Random Source
A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Valiant-Vazirani Lemmata for Various Logics