yusuke1997/dblp-id-title huggingface dataset:
Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms
Lifting randomized query complexity to randomized communication complexity
Random restrictions and PRGs for PTFs in Gaussian Space
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity
An exponential lower bound for homogeneous depth-5 circuits over finite fields
Lie algebra conjugacy
On Being Far from Far and on Dual Problems in Property Testing
Algorithms for SAT based on search in Hamming balls
Multiplayer parallel repetition for expander games
On testing bent functions
A game characterisation of tree-like Q-Resolution size
Computational Complexity, NP Completeness and Optimization Duality: A Survey
Counting in Uniform TC 0
Catalytic Approaches to the Tree Evaluation Problem
Privacy in Non-Private Environments
A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds
Computational and proof complexity of partial string avoidability
Improved low-degree testing and its applications
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
Solving Tree Evaluation in o(log n · log log n) space
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Hitting-sets for low-distance multilinear depth-3
Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept
PP-lowness and a simple definition of AWPP
Nearly-Linear Time Seeded Extractors with Short Seeds
Constructing elusive functions with help of evaluation mappings
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations
Succinct Zero-knowledge Proofs from One-way Functions: The Blackbox Way
An Information Complexity Approach to Extended Formulations
Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
On the Power of Extra Queries to Selective Languages
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes
SETH-hardness of Coding Problems
Superlinear lower bounds for multipass graph processing
Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries
A Polynomial Time Learner for a Subclass of Regular Patterns
Bicovering: Covering edges with two small subsets of vertices
The Log-Approximate-Rank Conjecture is False
Direct Product Testing With Nearly Identical Sets
One-way multi-party communication lower bound for pointer jumping with applications
The Möbius Function, Variations Ranks, and Theta(n)-Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem
Several notes on the power of Gomory-Chvatal cuts
Resolution with Counting: Lower Bounds over Different Moduli
Explicit lower bound for fooling polynomials by the sum of small-bias generators
On Non-Optimally Expanding Sets in Grassmann Graphs
Approximability of all finite CSPs in the dynamic streaming setting
Worst-Case to Average-Case Reductions via Additive Combinatorics
Explicit Capacity-Achieving List-Decodable Codes
Random Graphs and the Parity Quantifier
NQP = co-C = P
Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
Some Topics in Analysis of Boolean Functions
Higher-order Fourier analysis of F p n and the complexity of systems of linear forms
Non-uniform attacks against one-way functions and PRGs
AC0[p] Lower Bounds against MCSP via the Coin Problem
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity
Hardness Amplification in Proof Complexity
Lower Bounds for Monotone Counting Circuits
Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves
Proving NP-hardness for clique-width II: non-approximability of clique-width
Monotone expanders - constructions and applications
Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
A d 1/2+o(1) Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound
New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity
Interleaved Zero-Knowledge in the Public-Key Model
On approximating CSP-B
A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE
Super-cubic lower bound for generalized Karchmer-Wigderson games
An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
Approximating Longest Directed Path
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
Robust Self-Ordering versus Local Self-Ordering
Optimal bounds for monotonicity and Lipschitz testing over the hypercube
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin
Adaptive Algorithms for Online Decision Problems
The Range of Stability for Heterogeneous and FIFO Queueing Networks
On estimating the trace of quantum state powers
Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication
A Note on the Distance to Monotonicity of Boolean Functions
On Independent Sets, 2-to-2 Games and Grassmann Graphs
Time-Space Hardness of Learning Sparse Parities
On Approximability of Satisfiable k -CSPs: III
Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet
Linear Projections of the Vandermonde Polynomial
Graph Isomorphism and Circuit Size
Non-Interactive Delegation for Low-Space Non-Deterministic Computation
On $\epsilon$-sensitive monotone computations
Low degree almost Boolean functions are sparse juntas
Certificate games
A Composition Theorem for Randomized Query complexity
Corners in Quasirandom Groups via Sparse Mixing
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
Complexity of semi-algebraic proofs
Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions
Range Avoidance and Remote Point for Low-Depth Circuits: New Algorithms and Hardness
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
On the existence of strong proof complexity generators
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing
On polynomially many queries to NP or QMA oracles
Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
Linear systems over composite moduli
Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs
Clustering for Edge-Cost Minimization
Group representations that resist random sampling
Public-qubits versus private-coins
Witness Encryption and NP-hardness of Learning
Approximation of Boolean Functions by Combinatorial Rectangles
All Natural NPC Problems Have Average-Case Complete Versions
Optimal Error Resilience of Adaptive Message Exchange
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Universal Semantic Communication II: A Theory of Goal-Oriented Communication
A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness
On the complexity of enumerating ordered sets
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees
On coset leader graphs of structured linear codes
Bounds on 2-Query Locally Testable Codes with Affine Tests
Typed Monoids - An Eilenberg-like Theorem for non regular Languages
On the complexity of trial and error for constraint satisfaction problems
Interval graph representation with given interval and intersection lengths
Pseudorandomness, symmetry, smoothing: I
On Parallel Pseudorandom Generators
On the Computational Power of Winner-Take-All
Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity
ZPP is hard unless RP is small
Karchmer-Wigderson Games for Hazard-free Computation
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited
On the Circuit Complexity of Perfect Hashing
Measure on P revisited
Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique
Logspace Optimisation Problems and their Approximation Properties
Strong LTCs with inverse polylogarithmic rate and soundness
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
A reduction of proof complexity to computational complexity for AC 0 [p] Frege systems
Decision Tree Complexity versus Block Sensitivity and Degree
Computational Complexity on Computable Metric Spaces
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Black-White Pebbling is PSPACE-Complete
The black-box query complexity of polynomial summation
Scaled dimension and the Kolmogorov complexity of Turing hard sets
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
On the complexity of constructing pseudorandom functions (especially when they don't exist)
An operational characterization of mutual information in algorithmic information theory
Limitation on the rate of families of locally testable codes
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions
Universal Semantic Communication I
Arithmetic circuits: A chasm at depth three
Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings
Hard instances of algorithms and proof systems
Approximating SVP infty to within Almost-Polynomial Factors is NP-hard
Simplicity and Strong Reductions
On r -Simple k -Path
Deterministic list decoding of Reed-Solomon codes
Feasibly constructive proofs of succinct weak circuit lower bounds
Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits
Structural complexity of AvgBPP
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs
Overview of the doubly-efficient interactive proof systems of RRR
On the power assignment problem in radio networks
Probabilistically checkable proofs with low amortized query complexity
Approximate Degree-Weight and Indistinguishability
A simple proof that AND-compression of NP-complete problems is hard
On the Hardness of Approximating k-Dimensional Matching
Exponential time reductions and sparse languages in NEXP
Testing probability distributions using conditional samples
Average-Case Hardness of Proving Tautologies and Theorems
Breaking Square-Root Loss Barriers via Min-Entropy
A combinatorial MA-complete problem
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
Improved Lower Bounds for the Shortest Superstring and Related Problems
0-1 Integer Linear Programming with a Linear Number of Constraints
Low uniform versions of NC1
A Note on Realizing Iterated Multiplication by Small Depth Threshold Circuits
The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover
Testing in the bounded-degree graph model with degree bound two
Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity
Resolution and pebbling games
Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs
Non-Uniform Hardness for NP via Black-Box Adversaries
Classical Interaction Cannot Replace a Quantum Message
Nonnegative rank measures and monotone algebraic branching programs
Local list decoding with a constant number of queries
The "Log Rank" Conjecture for Modular Communication Complexity
Input locality and hardness amplification
Counting Unpredictable Bits: A Simple PRG from One-way Functions
A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester
Lifting to Parity Decision Trees Via Stifling
The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs
Search-to-Decision Reductions for Kolmogorov Complexity
On Searching Sorted Lists: A Near-Optimal Lower Bound
Algebraic Property Testing: The Role of Invariance
On multiparty communication with large versus unbounded error
On the expansion of the giant component in percolated (n,d,lambda) graphs
Isolation of Matchings via Chinese Remaindering
On The "Majority is Least Stable" Conjecture
Local reductions
Proving NP-hardness for clique-width I: non-approximability of sequential clique-width
A Note on One-way Functions and Sparse Languages
CSP Gaps and Reductions in the Lasserre Hierarchy
Exact Learning Boolean Functions via the Monotone Theory
Streaming algorithms for some problems in log-space
An Average-Case Lower Bound against ACC^0
Interactive Proofs For Distribution Testing With Conditional Oracles
Testing Conductance in General Graphs
Computation Over the Noisy Broadcast Channel with Malicious Parties
Why the Concept of Computational Complexity is Hard for Verifiable Mathematics
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
Approximating the Online Set Multicover Problems Via Randomized Winnowing
Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory
On the Cook-Mertz Tree Evaluation procedure
A Reducibility that Corresponds to Unbalanced Leaf-Language Classes
Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Non-approximability of the Permanent of Structured Matrices over Finite Fields
Equivalence Between Coding and Complexity Lower Bounds
On the Query Complexity of Quantum Learners
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck
Lower Bounds for Linear Transformed OBDDs and FBDDs
Polynomial Time with Restricted Use of Randomness
Bounded-depth Frege complexity of Tseitin formulas for all graphs
Homomorphisms in Graph Property Testing - A Survey
On the Computational Power of Recurrent Circuits of Spiking Neurons
Computational Bottlenecks for Evolvability
Progress on Polynomial Identity Testing - II
Better Secret-Sharing via Robust Conditional Disclosure of Secrets
More on Size and Width in QBF Resolution
Almost-catalytic Computation
Expander Random Walks: A Fourier-Analytic Approach
Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}
On Learning Branching Programs and Small Depth Circuits
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
A Robust Version of Hegedűs's Lemma, with Applications
On the Sample Complexity of MAX-CUT
Hardness of approximate hypergraph coloring
The Communication Complexity of Number-In-Hand Set Disjointness with No Promise
Security of Allmost ALL Discrete Log Bits
On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity
Characterizing Propositional Proofs as Non-Commutative Formulas
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)
Transparency Beyond VNP in the Monotone Setting
Multi Collision Resistant Hash Functions and their Applications
Reductions to the set of random strings: the resource-bounded case
Learning generalized depth-three arithmetic circuits in the non-degenerate case
Hardness magnification near state-of-the-art lower bounds
Security of the Most Significant Bits of the Shamir Message Passing Scheme
Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
On the Power of Las Vegas II: Two-Way Finite Automata
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem
Note on MAX 2SAT
Property Testing, PCP, andJuntas
Worst-case to Average-case reductions for subclasses of P
The Frequent Paucity of Trivial Strings
Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications
Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound
Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness
Channel assignment in wireless networks and classification of minimum graph homomorphism
Discovering the roots: Uniform closure results for algebraic classes under factoring
Extractors for Polynomial Sources over $\mathbb{F}_2$
Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Span programs and quantum query algorithms
Linear list-approximation for short programs (or the power of a few random bits)
Testing Graphs against an Unknown Distribution
Intrinsic Barriers and Practical Pathways for Human-AI Alignment: An Agreement-Based Complexity Analysis
Internal compression of protocols to entropy
Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Exotic quantifiers, complexity classes, and complete problems
Every set in P is strongly testable under a suitable encoding
Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in
LCC and LDC: Tailor-made distance amplification and a refined separation
The Deterministic and Randomized Query Complexity of a Simple Guessing Game
Small Bounded-Error Computations and Completeness
Extended Nullstellensatz proof systems
Separating NOF communication complexity classes RP and NP
Pseudorandom generators without the XOR Lemma
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?
On approximating the eigenvalues of stochastic matrices in probabilistic logspace
Simplyfing Armoni's PRG
A Note on Avoid vs MCSP
Optimal attribute-efficient learning of disjunction, parity, and threshold functions
On the Message Complexity of Interactive Proof Systems
Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes
Efficiently factoring polynomials modulo $p^4$
Probabilistic OBDDs: on Bound of Width versus Bound of Error
Computational aspects of feedback in neural circuits
Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
UTIME Easy-witness Lemma & Some Consequences
Shrinkage of De Morgan Formulae from Quantum Query Complexity
Seed Protecting Extractors
Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs
Public-key cryptography and invariant theory
Concurrent Knowledge-Extraction in the Public-Key Model
Efficient deterministic approximate counting for low degree polynomial threshold functions
Testing hereditary properties of ordered graphs and matrices
Testing linear inequalities of subgraph statistics
Sunflowers: from soil to oil
Fast Integer Multiplication using Modular Arithmetic
New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT
Homomorphic Encryption: from Private-Key to Public-Key
Sub-Constant Error Low Degree Test of Almost Linear Size
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
Efficient Linearization Implies the Multiphase Conjecture
More Verifier Efficient Interactive Protocols For Bounded Space
Local Maxima and Improved Exact Algorithm for MAX-2-SAT
On Complexity of Counting Fixed Points in Certain Classes of Graph Automata
Helly Circular-Arc Graph Isomorphism is in Logspace
Almost Completeness in Small Complexity Classes
Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications
Approximation Algorithm for the Max k-CSP Problem
Reflections on Proof Complexity and Counting Principles
A Note on Natural-Proofs for Super-Linear Lower Bounds for Linear Functions
Breaking Diffie-Hellman is no Easier than Root Finding
On the List-Decodability of Random Linear Codes
On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates
Trade-offs between Entanglement and Communication
When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---
Trading query complexity for sample-based testing and multi-testing scalability}
On Approximation Hardness of the Bandwidth Problem
It'll probably work out: improved list-decoding through random operations
Testing and Weight Distributions of Dual Codes
Bounded Matrix Rigidity and John's Theorem
Distance Estimators with Sublogarithmic Number of Queries
Efficient Interactive Coding Against Adversarial Noise
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Deterministic Hardness Amplification via Local GMD Decoding
Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs
Smoothed Analysis of the Height of Binary Search Trees
Proof complexity of natural formulas via communication arguments
Combinatorial Geometry of Graph Partitioning - I
Speedup for Natural Problems and coNP?=NP
Average Bias and Polynomial Sources
A Probabilistic Inequality with Applications to Threshold Direct-product Theorems
Maximum Matchings via Glauber Dynamics
Lower Bounds for (Non-monotone) Comparator Circuits
The normal form of reversible circuits consisting of CNOT and NOT gates
Automating Cutting Planes is NP-Hard
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs
Tight Computational Indistinguishability Bound of Product Distributions
Deterministic Extractors for Algebraic Sources
Extractors for Samplable Distribution with Polynomially Small Min-Entropy
Parallelism, Program Size, Time, and Temperature in Self-Assembly
Improved Approximate Degree Bounds For $k$-distinctness
The complexity of constraints on intervals and lengths
Total space in Resolution is at least width squared
Interactive Error Resilience Beyond 2/7
Decoding Downset codes over a finite grid
A hierarchy for (1,+k)-branching programs with respect to k
Concurrent Zero Knowledge without Complexity Assumptions
Gradual Small-Bias Sample Spaces
Learning Multivariate Polynomials from Substitution and Equivalence Queries
Flexible models for testing graph properties
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols
On the Possibility of Basing Cryptography on $\EXP \neq \BPP$
Non-commutative computations: lower bounds and polynomial identity testing
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem
The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions
Pebbling Meets Coloring : Reversible Pebble Game On Trees
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL
Beating Fredman-Komlós for perfect k-hashing
Lifting dichotomies
A simple proof of Bazzi's theorem
On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries
Graph Structure and Parity Games
Factorization norms and an inverse theorem for MaxCut
Randomness buys depth for approximate counting
Matrix Rigidity of Random Toeplitz Matrices
Combining LPs and Ring Equations via Structured Polymorphisms
Unambiguous parity-query complexity
Strict Self-Assembly of Discrete Sierpinski Triangles
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model
Deterministic Identity Testing for Sum of Read Once ABPs
Efficient indexing of necklaces and irreducible polynomials over finite fields
P=?NP
Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring
DNF Sparsification and a Faster Deterministic Counting
StUSPACE(log n) is Contained in DSPACE((log 2 n)/loglog n)
Extending Polynomial Calculus to $k$-DNF Resolution