yusuke1997/dblp-id-title huggingface dataset:
Extractors for circuit sources
Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication
NP-Hardness of Approximately Solving Linear Equations Over Reals
Communication Complexity is NP-hard
Uniform Hardness Amplification in NP via Monotone Codes
Constant Rate Codes for Adaptive Broadcasts Do Not Exist
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
Sharp Threshold Results for Computational Complexity
Redundancy for MaxSAT
A Graph Spectral Approach for Computing Approximate Nash Equilibria
The Oracle Derandomization Hypothesis is False (And More) Assuming No Natural Proofs
An elementary proof of anti-concentration of polynomials in Gaussian variables
Approximate Counting small subgraphs of bounded treewidth and related problems
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree
K-Monotonicity is Not Testable on the Hypercube
QBF Merge Resolution is powerful but unnatural
Expanding Generator Sets for Solvable Permutation Groups
Computing on the edge of chaos: Structure and randomness in encrypted computation
Explicit Extremal Designs and Applications to Extractors
A note on circuit lower bounds from derandomization
How to get more mileage from randomness extractors
Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
Quadratic maps are hard to sample
On Parallelizing Streaming Algorithms
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
A new upper bound on the query complexity for testing generalized Reed-Muller codes
The Communication Complexity of the Exact Gap-Hamming Problem
Patterned non-determinism in communication complexity
On the information leakage of public-output protocols
A o(n) monotonicity tester for Boolean functions over the hypercube
A new class of rank-metric codes and their list decoding beyond the unique decoding radius
Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete
Approximating the SVP to within a factor (1 + 1/dim epsilon ) is NP-hard under randomized reductions
Dual polynomials and communication complexity of XOR functions
On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes
Testing Linear Properties: Some general themes
Classical simulation of one-query quantum distinguishers
A Nearly Tight Bound for Private Information Retrieval Protocols
Equality is Far Weaker Than Constant-Cost Communication
On Proof complexity of Resolution over Polynomial Calculus
Reductions Between Classification Tasks
Clique is hard to approximate within n 1-epsilon
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Direct Sums in Randomized Communication Complexity
The Meta-Complexity of Secret Sharing
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems
On blocky ranks of matrices
The Spectrum of Small DeMorgan Formulas
Meta-Mathematics of Computational Complexity Theory
Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
How To Simulate It - A Tutorial on the Simulation Proof Technique
Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability
Approximating CSPs using LP Relaxation
Towards efficient constructions of hitting sets that derandomize BPP
The Entropy Influence Conjecture Revisited
An exponential lower bound for the sum of powers of bounded degree polynomials
Graph Properties that Facilitate Travelling
Even quantum advice is unlikely to solve PP
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Encodings and the Tree Evaluation Problem
Leakage-Resilient Secret Sharing
On the optimal compression of sets in PSPACE
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
An application of matroid theory to the SAT problem
A Polynomial Time Approximation Scheme for Metric MIN-BISECTION
Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
Constant Query Local Decoding Against Deletions Is Impossible
Separation of the factorization norm and randomized communication complexity
Approximation Hardness of Short Symmetric Instances of MAX-3SAT
Coin Theorems and the Fourier Expansion
Property and Equivalence Testing on Strings
On One-way Functions from NP-Complete Problems
Leakage-Resilient Hardness v.s. Randomness
Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources
An enumerable undecidable set with low prefix complexity: a simplified proof
Relative Discrepancy does not separate Information and Communication Complexity
Dynamic Process Graphs and the Complexity of Scheduling
Some Lower Bound Results for Set-Multilinear Arithmetic Computations
A Note on Testing Truthfulness
Finding Significant Fourier Transform Coefficients Deterministically and Locally
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds
On the VNP-hardness of Some Monomial Symmetric Polynomials
Circuit lower bounds and linear codes
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate
Inapproximability of Feedback Vertex Set for Bounded Length Cycles
Non-Interactive Non-Malleability from Quantum Supremacy
Locally testable codes via high-dimensional expanders
Generic yet Practical ZK Arguments from any Public-Coin HVZK
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
Approximations by OBDDs and the variable ordering problem
Testing the independence number of hypergraphs
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions
Octahedral Tucker is PPA-Complete
Improved decoding of Reed-Solomon and algebraic-geometric codes
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
Generalized Matrix Completion and Algebraic Natural Proofs
A Gap in Average Proof Complexity
Private Computation - k-connected versus 1-connected Networks
Computing Equilibria: A Computational Complexity Perspective
Error Reduction For Weighted PRGs Against Read Once Branching Programs
Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Algebraic Pseudorandomness in VNC 0
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs
BQP and the Polynomial Hierarchy
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent
Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP
Hardness of Directed Routing with Congestion
On determinism versus unambiquous nondeterminism for decision trees
An upper bound on $\ell_q$ norms of noisy functions
A new transference theorem and applications to Ajtai's connection factor
Approximating Large Powers of Stochastic Matrices in Small Space
Accelerated Slide- and LLL-Reduction
Refuting approaches to the log-rank conjecture for XOR functions
Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances"
A Combinatorial Characterization of Treelike Resolution Space
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
A Structured View on Weighted Counting with Relations to Quantum Computation and Applications
Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
On Testing Expansion in Bounded-Degree Graphs
A Duality Between One-Way Functions and Average-Case Symmetry of Information
On the Unprovability of Circuit Size Bounds in Intuitionistic S 1 2
Separations in communication complexity using cheat sheets and information complexity
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds
Deterministic Black-Box Identity Testing pi-Ordered Algebraic Branching Programs
Proof Complexity of Symmetry Learning in QBF
A Logical Characteristic of Read-Once Branching Programs
Topology and adjunction in promise constraint satisfaction
Limitations of sum of products of Read-Once Polynomials
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
Towards Dimension Expanders Over Finite Fields
Pure Nash equilibria in games with a large number of actions
Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)
On Data Structure Tradeoffs and an Application to Union-Find
Non-Malleable Codes Against Constant Split-State Tampering
An Improved Derandomization of the Switching Lemma
Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations
An efficient quantum parallel repetition theorem and applications
An Exposition of Bourgain's 2-Source Extractor
Extractors for Adversarial Sources via Extremal Hypergraphs
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
Speeding up Evolutionary Algorithms by Restricted Mutation Operators
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Lower Bounds on the Overhead of Indistinguishability Obfuscation
A Characterization of Strong Approximation Resistance
Schur Polynomials do not have small formulas if the Determinant doesn't!
Near-Optimal Averaging Samplers
On Maximally Recoverable Local Reconstruction Codes
How much randomness is needed to convert MA protocols to AM protocols?
Bounds on Linear Codes for Network Multicast
New hardness results for graph and hypergraph colorings
The Pattern Matrix Method for Lower Bounds on Quantum Communication
A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Submodular Functions Are Noise Stable
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\epsilon} n}$
Relaxed partition bound is quadratically tight for product distributions
On the proper learning of axis parallel concepts
Limits of structures and Total NP Search Problems
Samplers and extractors for unbounded functions
Non-constant Degree Lower Bounds imply linear Degree Lower Bounds
Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
Pseudorandom Generators for Read-Once Branching Programs, in any Order
An O(n 0.4732 ) upper bound on the complexity of the GKS communication game
Interactive Compression for Product Distributions
A Note on the Power of Extra Queries to Membership Comparable Sets
Dispersers for affine sources with sub-polynomial entropy
Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction)
On locally-characterized expander graphs (a survey)
A story of AM and Unique-SAT
PPSZ on CSP Instances with Multiple Solutions
Better Extractors for Better Codes?
Extending Merge Resolution to a Family of Proof Systems
Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
Optimal testing of multivariate polynomials over small prime fields
On the Average-Case Complexity of Property Testing
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability
Pseudorandomness for Width 2 Branching Programs
A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
Delegating Computations with (almost) Minimal Time and Space Overhead
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Complexity and Probability of some Boolean Formulas
Generalized Compact Knapsacks are Collision Resistant
A note on average-case sorting
Inverting onto functions might not be hard
An O(n ε ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
(2+ε)-SAT is NP-hard
Sum-of-squares proofs and the quest toward optimal algorithms
Lifting Nullstellensatz to Monotone Span Programs over Any Field
On Lifting Lower Bounds for Noncommutative Circuits using Automata
Earth Mover Distance over High-Dimensional Spaces
The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model
Better gates can make fault-tolerant computation impossible
A primer on the closure of algebraic complexity classes under factoring
Perfect zero knowledge for quantum multiprover interactive proofs
The Geometry of Rounding
Log-space Constructible Universal Traversal Sequences for Cycles of Length O(n 4.03 )
On List Decoding Transitive Codes From Random Errors
Dobrushin conditions and Systematic Scan
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Lower bounds for Polynomial Calculus with extension variables over finite fields
Improved concrete efficiency and security analysis of Reed-Solomon PCPPs
The Freiman-Ruzsa Theorem in Finite Fields
Unbounded-Error Communication Complexity of Symmetric Functions
Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques
Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems
Quantum and randomized communication complexity of XOR functions in the SMP model
Modulo Information from Nonadaptive Queries to NP
Cryptographic Hardness Results for Learning Intersections of Halfspaces
Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs
Symmetric LDPC codes are not necessarily locally testable
Perfect Matching in Bipartite Planar Graphs is in UL
On frequent sets of Boolean matrices
A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths
Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity
Relativized Worlds Without Worst-Case to Average-Case Reductions for NP
Circuits Resilient to Short-Circuit Errors
Improved Lower Bounds for Resolution over Linear Inequalities
An overview of some semantic and syntactic complexity classes
Testing Assignments of Boolean CSPs
On Approximability of Satisfiable k -CSPs: II
An Exponential Time/Space Speedup For Resolution
Online Capacity Maximization in Wireless Networks
A Note on Amplifying the Error-Tolerance of Locally Decodable Codes
Toward better depth lower bounds: the XOR-KRW conjecture
A complex analogue of Toda's Theorem
Topology inside NC 1
Optimal proof systems for Propositional Logic and complete sets
A second-order system for polynomial-time reasoning based on Graedel's theorem
Subspace Evasive Sets
Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size
A Quantum Time-Space Lower Bound for the Counting Hierarchy
The Lovasz number of random graph
Rounding Sum-of-Squares Relaxations
Derandomizing Isolation Lemma for K 3,3 -free and K 5 -free Bipartite Graphs
The Complexity of Two Register and Skew Arithmetic Computation
On segregators, separators and time versus space
8/7-Approximation Algorithm for (1,2)-TSP
Formulas vs. Circuits for Small Distance Connectivity
Near Coverings and Cosystolic Expansion - an example of topological property testing
Classical and quantum partition bound and detector inefficiency
Massive Online Teaching to Bounded Learners
Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model
Downward self-reducibility in the total function polynomial hierarchy
On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic
andom walks and forbidden minors II: A poly(dε -1 )$-query tester for minor-closed properties of bounded degree graphs
Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs
An Approximation Algorithm for the Bandwidth Problem on Dense Graphs
Finite Limits and Monotone Computations
On quantum versus classical query complexity
XOR Lemmas for Resilient Functions Against Polynomials
Correctness and Corruption of Locally Decodable Codes
Composition and Simulation Theorems via Pseudo-random Properties
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
Approximation Schemes for Preemptive Weighted Flow Time
Kernels for the Dominating Set Problem on Graphs with an Excluded Minor
An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
Dependent Random Graphs and Multiparty Pointer Jumping
A Duality Between Depth-Three Formulas and Approximation by Depth-Two
On the symmetries of design polynomials
Understanding Nullstellensatz for QBFs
The weakness of CTC qubits and the power of approximate counting
Explicit Strong LTCs with inverse poly-log rate and constant soundness
Algorithms from Natural Lower Bounds
VC Dimension of Sigmoidal and General Pfaffian Networks
Online Algorithms for Self-Organizing Sequential Search - A Survey
Designing Strassen's algorithm
Security Levels in Steganography - Insecurity does not Imply Detectability
The Number of Knight's Tours Equals 33,439,123,484,294 - Counting with Binary Decision Diagrams
Tight lower bounds for adaptive linearity tests
Orthogonal Vectors is hard for first-order properties on sparse graphs
The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard
Hardness of learning noisy halfspaces using polynomial thresholds
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
Counting with Counterfree Automata
Candidate One-Way Functions Based on Expander Graphs
A proof complexity conjecture and the Incompleteness theorem
From DNF compression to sunflower theorems via regularity
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits
Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search
A Fourier-analytic approach to Reed-Muller decoding
Cosystolic Expanders over any Abelian Group
On Spanning Cacti and Asymmetric TSP
A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Lower Bound Methods for Sign-rank and their Limitations
Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions
A Tight Lower Bound of Ω(log n) for the Estimation of the Number of Defective Items
Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials
IPS Lower Bounds for Formulas and Sum of1 ROABPs
Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees
The complexity of 3-colouring H -colourable graphs
Faster exponential time algorithms for the shortest vector problem
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
Multisource algorithmic information theory
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Succinct Representation and Leaf Languages
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Testing Expansion in Bounded Degree Graphs
Rainbow coloring hardness via low sensitivity polymorphisms
PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials
On The Sensitivity Conjecture
A (De)constructive Approach to Program Checking
From logarithmic advice to single-bit advice
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums
Batch Codes through Dense Graphs without Short Cycles
On Proximity Oblivious Testing
Testing of exponentially large codes, by a new extension to Weil bound for character sums
SOS lower bound for exact planted clique
Hardness of Learning DNFs using Halfspaces
Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs
Bounds for Bilinear Complexity of Noncommutative Group Algebras
Deterministic Construction of a high dimensional l p section in l 1 n for any p<2
Instance Compression for the Polynomial Hierarchy and Beyond
Combinatorial PCPs with efficient verifiers
The Fine-Grained Complexity of Strengthenings of First-Order Logic
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes
Barriers for Rectangular Matrix Multiplication
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Randomness Extraction in AC 0 and with Small Locality
Dag-like Communication and Its Applications
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity
Identity Testing for +-Regular Noncommutative Arithmetic Circuits
On the Probabilistic Degrees of Symmetric Boolean functions
Character sums over AG codes
Local Testing and Decoding of High-Rate Error-Correcting Codes
A Polynomial Time Approximation Scheme for Subdense MAX-CUT
Partition into k-vertex subgraphs of k-partite graphs
Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions
Property Testing of Equivalence under a Permutation Group Action
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies
BQP and PPAD
Two-Sorted Theories for L, SL, NL and P
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
Proper PAC learning is compressing
Instance-Hiding Interactive Proofs
Lower Bounds against the Ideal Proof System in Finite Fields
Parametric Duality: Kernel Sizes and Algorithmics
A tighter lower bound on the circuit size of the hardest Boolean functions
AC 0 [p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
Codes over integers, and the singularity of random matrices with large entries
Sign-Rank of $k$-Hamming Distance is Constant
One-way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity
Decidability of Non-Interactive Simulation of Joint Distributions
Fishing out Winners from Vote Streams
The Depth Irreducibility Hypothesis
A New Look at Some Classical Results in Computational Complexity
Completeness in Two-Party Secure Computation - A Computational View
Improved Bounds on the Space Complexity of Circuit Evaluation
On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets
Space-bounded quantum interactive proof systems
A Simple Algorithm for Undirected Hamiltonicity
Fractional Pseudorandom Generators from the $k$th Fourier Level
Statistical Algorithms and a Lower Bound for Planted Clique
Solvable Group Isomorphism is (almost) in NP\cap coNP
Randomized communication complexity of appropximating Kolmogorov complexity
Monotone complexity and the rank of matrices
On Constructing 1-1 One-Way Functions
On defining PPT-search problems and PPT-optimization problems
Are stable instances easy?
QCDCL with Cube Learning or Pure Literal Elimination - What is best?
Extracting All the Randomness and Reducing the Error in Trevisan's Extractors
Pseudo-derandomizing learning and approximation
Monotone Circuit Complexity of Matching
Compressing interactive communication under product distributions
Limitations of Linear Programming Techniques for Bounded Color Matchings
Monotone Branching Programs: Pseudorandomness and Circuit Complexity
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques
New Polynomial-Depth Res(+) Lower Bounds
On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")