yusuke1997/dblp-id-title huggingface dataset:
On the Complexity of Computing and Learning with Multiplicative Neural Networks
On the sum of L1 influences
Finding monotone patterns in sublinear time
Non-malleable Codes from Additive Combinatorics
DLOGTIME-Proof Systems
On the Sum of Square Roots of Polynomials and related problems
Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity
Approximability of Hypergraph Minimum Bisection
Disjointness is hard in the multi-party number-on-the-forehead model
Limits of provable security for homomorphic encryption
A Lower Bound for k -DNF Resolution on Random CNF Formulas via Expansion
Some properties are not even partially testable
Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP
Factoring groups efficiently
Disproving the single level conjecture
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates
The Approximate Rank of a Matrix and its Algorithmic Applications
Exact OBDD Bounds for some Fundamental Functions
Non-Malleable Extractors for Entropy Rate <1/2
A super-polynomial separation between resolution and cut-free sequent calculus
An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers
Lower Bounds for Linear Operators
Black-Box Identity Testing of Depth-4 Multilinear Circuits
Query complexity of matroids
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed
Simultaneous Resettability from Collision Resistance
Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk
Tighter Relations Between Sensitivity and Other Complexity Measures
Constraint satisfaction: a personal perspective
On Non-automatizability in PAC-Semantics
Linear programming bounds for codes via a covering argument
On the complexity of cutting plane proofs using split cuts
On Closure Properties of GapL
Explicit Non-Malleable Codes Resistant to Permutations
On Optimal Multi-Dimensional Mechanism Design
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
Determinism Versus Nondeterminism with Arithmetic Tests and Computation
QRAT Polynomially Simulates Merge Resolution
Reviewing Bounds on the Circuit Size of the Hardest Functions
Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games
Min-Entropic Optimality
Optimal quantile estimation: beyond the comparison model
On Multi-Partition Communication Complexity of Triangle-Freeness
Deterministic vs Non-deterministic Graph Property Testing
Logic, Graphs, and Algorithms
Derandomization: A Brief Overview
Composing Low-Space Algorithms
On Rich $2$-to-$1$ Games
Arithmetizing classes around NC^1 and L
Constraint Satisfaction on Finite Groups with Near Subgroups
Direct sum testing - the general case
Lower bounds: from circuits to QBF proof systems
On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity
Nash Equilibria in Graphical Games on Trees Revisited
A remark on nondecidabilities of the initial value problem of ODEs
Complexity of distributions and average-case hardness
Approximating Operator Norms via Generalized Krivine Rounding
An improved bound on correlation between polynomials over Z_m and MOD_q
Deterministic Turing Machines in the Range between Real-Time and Linear-Time
Approximation of Global MAX-CSP Problems
Permanental rank versus determinantal rank of random matrices over finite fields
Weak Composite Diffie-Hellman is not Weaker than Factoring
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)
Pseudorandom bits for non-commutative programs
On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting
(Nondeterministic) Hardness vs. Non-Malleability
On the query complexity for Showing Dense Model
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat
Swap cosystolic expansion
On Matrix Rigidity and the Complexity of Linear Forms
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
Closures and dichotomies for quantified constraints
Improved inapproximability factors for some Sigma 2 p minimization problems
Boolean functions with a vertex-transitive group of automorphisms
The uniform distribution is complete with respect to testing identity to a fixed distribution
Indistinguishability Obfuscation Does Not Reduce to Structured Languages
Finding forbidden minors in sublinear time: a O(n 1/2+o(1) )-query one-sided tester for minor closed properties on bounded degree graphs
Finding Favorites
Mixing Implies Strong Lower Bounds for Space Bounded Learning
Pr-ZSUBEXP is not contained in Pr-RP
How to Find Water in the Ocean: A Survey on Quantified Derandomization
New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method
Some dichotomy theorems for neural learning problems
On Interactive Coding Schemes with Adaptive Termination
On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances
Space-bounded quantum state testing via space-efficient quantum singular value transformation
On small-depth Frege proofs for Tseitin for grids
Asymptotically good large-alphabet LDCs with polylogarithmic query complexity
On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization
Some structural properties of low rank matrices related to computational complexity
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
New Independent Source Extractors with Exponential Improvement
On the Algorithmic Content of Quantum Measurements
Computing polynomials with few multiplications
Limits on the Hardness of Lattice Problems in ℓ p Norms
Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle
QMA Lower Bounds for Approximate Counting
Breaking the quadratic barrier for 3-LCCs over the Reals
From absolute distinguishability to positive distinguishability
Efficient Communication Using Partial Information
Recursive analytic functions of a complex variable
A tight characterization of NP with 3 query PCPs
Reconstruction of ΣΠΣ(2) Circuits over Reals
Limits of Random Oracles in Secure Computation
A generalization of Lutz's measure to probabilistic classes
An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions
Crown reductions for the Minimum Weighted Vertex Cover problem
Correlation bounds against polynomials
What Can be Efficiently Reduced to the Kolmogorov-Random Strings?
On Approximation Lower Bounds for TSP with Bounded Metrics
On algebraic branching programs of small width
On the Time Complexity of Feasible Proofs
The Learnability of Quantum States
Quantum Fingerprints that Keep Secrets
More on $AC^0[\oplus]$ and Variants of the Majority Function
Read-Once Polynomial Identity Testing
An Ultimate Trade-Off in Propositional Proof Complexity
Improved Soundness for QMA with Multiple Provers
On basing ZK != BPP on the hardness of PAC learning
On the Ring Isomorphism & Automorphism Problems
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size
Graph Isomorphism for K 3,3 -free and K 5 -free graphs is in Log-space
Information Complexity for Multiparty Communication
Logical operations and Kolmogorov complexity. II
Probabilistically Checkable Proofs The Easy Way
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
Verification of Statistical Properties: Redefining the Possible
The Complexity of Forecast Testing
On the structure of Solution-Graphs for Boolean Formulas
Short Locally Testable Codes and Proofs (Survey)
Pseudodeterministic Communication Complexity
Properties and Applications of Boolean Function Composition
Degree 2 lower bound for Permanent in arbitrary characteristic
Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds
Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem
On sketching approximations for symmetric Boolean CSPs
Sparse Hard Sets for P Yields Space-Efficient Algorithms
The Security of all RSA and Discrete Log Bits
Pseudorandom Functions: Three Decades Later
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems
A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory
Pseudorandom Generators for Group Products
The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function
Improved Approximation Lower Bounds on Small Occurrence Optimization
Shortest path length with bounded-alternation (min, +) formulas
Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE
Improved Search-to-Decision Reduction for Random Local Functions
Doubly-Efficient Pseudo-Deterministic Proofs
Direct Sum Fails for Zero Error Average Communication
AC 0 Pseudorandomness of Natural Operations
Challenges in computational lower bounds
Streaming beyond sketching for Maximum Directed Cut
Non-Interactive RAM and Batch NP Delegation from any PIR
Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost
Anti-concentration in most directions
Fully Homomorphic Encryption without Bootstrapping
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas
On Branching Programs With Bounded Uncertainty
Inapproximability of Matrix p→q Norms
Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
Simple Affine Extractors using Dimension Expansion
PCPs via low-degree long code and hardness for constrained hypergraph coloring
On Approximation Intractability of the Bandwidth Problem
Competing Provers Protocols for Circuit Evaluation
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Constructions of low-degree and error-correcting epsilon-biased sets
Randomized query complexity of sabotaged and composed functions
Random CNFs are Hard for Cutting Planes
A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information
The Spectral Method for Mixture Models
Graphs of Bounded Treewidth can be Canonized in AC 1
Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications
An Interactive Information Odometer with Applications
On Promise Problems (a survey in memory of Shimon Even [1935-2004])
The Maximum Communication Complexity of Multi-party Pointer Jumping
Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications
Relating two width measures for resolution proofs
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
(A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games
Almost quadratic gap between partition complexity and query/communication complexity
Efficient Polynomial Identity Testing Over Nonassociative Algebras
Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters
Tight Parallel Repetition Theorems for Public-coin Arguments
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds
Sound 3-query PCPPs are Long
Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids
Generalized comparison trees for point-location problems
Rank Bounds for a Hierarchy of Lovász and Schrijver
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.
Top-down induction of decision trees: rigorous guarantees and inherent limitations
Communication Complexity and Secure Function Evaluation
Random Sampling and Approximation of MAX-CSP Problems
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures
A parallel repetition theorem for all entangled games
The Coin Problem in Constant Depth: Sample Complexity and Parity gates
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
Arithmetic circuits with locally low algebraic rank
Poly-logarithmic independence fools AC0 circuits
On Computational Power of Partially Blind Automata
Separations between Combinatorial Measures for Transitive Functions
Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling
On the Approximability of the Multi-dimensional Euclidean TSP
On obtaining pseudorandomness from error-correcting codes.
Sensitivity lower bounds from linear dependencies
Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More
On the Fourier spectrum of Monotone Functions
Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions
On the hardness of learning sparse parities
On the relaxed LDC of BGHSV: A survey that corrects the record
A Noise Resilient Transformation for Streaming Algorithms
Recycling Queries in PCPs and in Linearity Tests
Eliminating Intermediate Measurements using Pseudorandom Generators
Lower Bounds for Sums of Products of Low arity Polynomials
Tight lower bounds for the asymmetric k-center problem
A stochastic calculus approach to the oracle separation of BQP and PH
On the Hardness of the Noncommutative Determinant
Upper and Lower Bounds for the Linear Ordering Principle
Approximating Hyper-Rectangles: Learning and Pseudo-random Sets
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search
Theory Revision with Queries: Horn, Read-once, and Parity Formulas
Improved Debordering of Waring Rank
On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits
The Resolution Complexity of Random Graph k-Colorability
On-line Learning of Rectangles in Noisy Environments
A Note on the Complexity of the Reachability Problem for Tournaments
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates
Forrelation is Extremally Hard
Planarity, Exclusivity, and Unambiguity
The Complexity of Finding S -factors in Regular Graphs
Extractors: Low Entropy Requirements Colliding With Non-Malleability
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates
XOR Codes and Sparse Random Linear Equations with Noise
The Size of SPP
Faster SDP hierarchy solvers for local rounding algorithms
Quantum Lovász Local Lemma: Shearer's Bound is Tight
Classification of Search Problems and Their Definability in Bounded Arithmetic
Lindstroem Quantifiers and Leaf Language Definability
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Coboundary and cosystolic expansion without dependence on dimension or degree
Decoding Multivariate Multiplicity Codes on Product Sets
The communication complexity of correlation
Time-Bounded Universal Distributions
Explicit Optimal hardness via Gaussian stability results
Circuit Complexity of Bounded Planar Cutwidth Graph Matching
Circuit Minimization Problem
One-Way Functions and Polynomial Time Dimension
Kakeya sets, new mergers and old extractors
Hardness amplification via space-efficient direct products
Universal Locally Testable Codes
Range Avoidance in Boolean Circuits via Turan-type Bounds
The Complexity of the Hajos Calculus for Planar Graphs
Lower Bounds for (MOD p -- MOD m) Circuits
Lower bounds for samplers and data structures via the cell-probe separator
Lower bound for communication complexity with no public randomness
An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX
Computing Requires Larger Formulas than Approximating
The space complexity of recognizing well-parenthesized expressions
A new algorithm for optimal constraint satisfaction and its implications
Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs
Separating Monotone VP and VNP
The List-Decoding Size of Reed-Muller Codes
New lower bounds for privacy in communication protocols
The power of the Binary Value Principle
Finding Primitive Roots Pseudo-Deterministically
A Simple Supercritical Tradeoff between Size and Height in Resolution
Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs
An additive combinatorics approach to the log-rank conjecture in communication complexity
Affine projections of polynomials
Pseudo-random functions and uniform learnability
NP-hard Sets Are Superterse unless NP Is Small
Hardness and Non-Approximability of Bregman Clustering Problems
A Lower Bound on the Trace Norm of Boolean Matrices and its Applications
Entropy of operators or why matrix multiplication is hard for small depth circuits
Radical Sylvester-Gallai for Cubics
The Ordering Principle in a Fragment of Approximate Counting
Sign rank vs Discrepancy
Inverse Problems in Approximate Uniform Generation
Sensitivity Lower Bounds for Approximaiton Algorithms
On Fractional Block Sensitivity
Raz-McKenzie simulation with the inner product gadget
Further extensions of Clifford circuits and their classical simulation complexities
Non-black-box Worst-case to Average-case Reductions within NP
Inapproximability of Combinatorial Optimization Problems
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Irreducibility and deterministic r-th root finding over finite fields
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic
Finite state verifiers with constant randomness
CHS-alike 1/O(log log n)-rate tree codes from elementary binary shifts
Quantum and Classical Tradeoffs
The KW Games as a Teaser
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
From Randomness Extraction to Rotating Needles
Multi-conditional Descriptions and Codes in Kolmogorov Complexity
Quantum lower bound for inverting a permutation with advice
Mixing in non-quasirandom groups
On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings
On the query complexity of testing local graph properties in the bounded-degree graph model
Unambiguous DNFs from Hex
Collision-Free Hashing from Lattice Problems
A Complete Problem for Statistical Zero Knowledge
Batch Proofs are Statistically Hiding
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems
The multiparty communication complexity of interleaved group products
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
The Fourier structure of low degree polynomials
On the AC 0 [⊕] complexity of Andreev's Problem
A logic for PTIME and a parameterized halting problem
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups
Agreement tests on graphs and hypergraphs
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors
On the complexity of computing a random Boolean function over the reals
Proof Systems That Tightly Characterise Model Counting Algorithms
Derandomization Under Different Resource Constraints
Lower Bounds for RAMs and Quantifier Elimination
On the logspace shortest path problem
Efficient Quantum Hermite Transform
Free Binary Decision Diagrams for Computation of EAR n
Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP
A Technique for Hardness Amplification Against $\mathrm{AC}^0$
Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
Explicit rank-metric codes list-decodable with optimal redundancy
Complexity-Theoretic Inductive Inference
On Chvatal Rank and Cutting Planes Proofs
Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof
On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm
New ways of studying the BPP = P conjecture
Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Recovery Reductions, Conjectures, and Barriers
Fourier conjectures, correlation bounds, and Majority
Tree Evaluation is in Space O(log n · log log n)
Quantum Lower Bound for Recursive Fourier Sampling
Interactive Channel Capacity
Optimal Proof Systems and Complete Languages
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Impossibility of Derandomizing the Isolation Lemma for all Families
A sampling lower bound for permutations
Improved Maximally Recoverable LRCs using Skew Polynomials
Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic
Average-case rigidity lower bounds
Exact constructive and computable dimensions
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
A Study of Error Reduction Polynomials
Determinant equivalence test over finite fields and over ℚ
Depth lower bounds in Stabbing Planes for combinatorial principles
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ p Norms
On the decomposition of lattices
Ultra-Sparse Expanders and the Free Method
Expansion without Connectivity: A Property Testing Perspective
An optimal lower bound for monotonicity testing over hypergrids
Capacity of Non-Malleable Codes
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover
A nearly-4logn depth lower bound for formulas with restriction on top
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent
One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
A Parallel Repetition Theorem for the GHZ Game
Sylvester-Gallai type theorems for approximate collinearity
Efficiently Approximable Real-Valued Functions
A Simple Proof of Vyalyi's Theorem and some Generalizations
Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
Algebraic Independence in Positive Characteristic - A p-Adic Calculus
Compressibility Lower Bounds in Oracle Settings
S_2 p \subseteq ZPP NP
The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics
Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders
Symmetric Logspace is Closed Under Complement
Computing the Elementary Symmetric Polynomials in Positive Characteristics
Testing the Expansion of a Graph
Constant-depth circuits for polynomial GCD over any characteristic
NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
A Short Implicant of CNFs with Relatively Many Satisfying Assignments
Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
Improved Constructions of Two-Source Extractors
Ideal-theoretic Explanation of Capacity-achieving Decoding
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)
Strongly Exponential Separation Between Monotone VP and Monotone VNP
Pseudorandomness, symmetry, smoothing: II
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
Computing Igusa's local zeta function of univariates in deterministic polynomial-time
On testing affine-invariant properties
Breaking local symmetries can dramatically reduce the length of propositional refutations
Strong LTCs with inverse poly-log rate and constant soundness