yusuke1997/dblp-id-title huggingface dataset:
Simplifying Nested Radicals and Solving Polynomials by Radicals in Minimum Depth
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
Towards Analysing Sequences of Operations for Dynamic Data Structures (Preliminary Version)
New Results for Learning Noisy Parities and Halfspaces
On the Local Structure of Stable Clustering Instances
On the Randomized Complexity of Volume and Diameter
Monte-Carlo Algorithms for Enumeration and Reliability Problems
Optimal Auctions vs. Anonymous Pricing
On the Union of Cylinders in Three Dimensions
The Art Gallery Theorem for Polygons With Holes
Honest Bounds for Complexity Classes of Recursive Functions
Integral Geometry of Higher-Dimensional Polytopes and the Average Case in Combinatorial Optimization
Deciding Properties of Polynomials Without Factoring
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
A Characterization of Testable Hypergraph Properties
Spectral Analysis of Matrix Scaling and Operator Scaling
Generalised Symmetries of Polynomials in Algebraic Complexity
Switch Scheduling via Randomized Edge Coloring
A PTAS for Computing the Supremum of Gaussian Processes
Nonembeddability theorems via Fourier analysis
Improved Lower Bounds for Submodular Function Minimization
On Minimal Modulo 2 Sums of Products for Switching Functions
Complexity Measures for Public-Key Cryptosystems (Preliminary Report)
Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs)
The profile technique for the design of threshold device logic
Roots of Star Events
Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract)
Planar Point Location in Sublogarithmic Time
On Equations Including String Variables
Computing with Snakes in Directed Networks of Automata (Extended Abstract)
Approximation Limits of Linear Programs (Beyond Hierarchies)
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law
On the Network Complexity of Selection
Fast Generalized DFTs for all Finite Groups
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
Theory of Sponsored Search Auctions
61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020
Constant Depth Circuits and the Lutz Hypothesis
The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant
Information Theory and the Complexity of Switching Networks (Preliminary Version)
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
Tight Bounds for Sorting Under Partial Information
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)
On-line Load Balancing (Extended Abstract)
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians
Computational Complexity and the Classification of Finite Simple Groups
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Counting Rational Points on Curves over Finite Fields (Extended Abstract)
Syntactic Clues
Generalized automata and their information losslessness
Random Formulas, Monotone Circuits, and Interpolation
Quantum Speed-Ups for Solving Semidefinite Programs
A Simple Local-Control Approximation Algorithm for Multicommodity Flow
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
A Temporal Logic to Deal with Fairness in Transition Systems
Approximation Algorithms for Scheduling on Multiple Machines
Cache-Oblivious B-Trees
Optimal Allocation of Computational Resources in VLSI
Computable Obstructions to Wait-free Computability
Constraint Satisfaction Problems of Bounded Width
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Local Graph Partitioning using PageRank Vectors
Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables
IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016
35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
Efficient Density Evaluation for Smooth Kernels
Amplification and Percolation
A computer program for the synthesis of combinational switching circuits
Delayed Information and Action in On-line Algorithms
Approximation Algorithms for Scheduling Unrelated Parallel Machines
Better Bounds for Threshold Formulas
Sublinear Algorithms for Local Graph Centrality Estimation
Minimean Optimality in Sorting Algorithms
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion
Nonexpressibility of Fairness and Signaling
Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Proximity Gaps for Reed-Solomon Codes
Representative Sets and Irrelevant Vertices: New Tools for Kernelization
A Faster PSPACE Algorithm for Deciding the Existential Theory of the Reals
Quasilinear Time List-Decodable Codes for Space Bounded Channels
Storing a Sparse Table with O(1) Worst Case Access Time
MAJORITY-3SAT (and Related Problems) in Polynomial Time
Noise and the Frontier of Quantum Supremacy
Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes
On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic
Relativizing Time and Space (Preliminary Report)
Split and Join: Strong Partitions and Universal Steiner Trees for Graphs
Pattern Matching for Spatial Point Sets
On Driving Many Long Lines in a VLSI Layout
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
Graph Products and Chromatic Numbers
Approximating the Volume of Definable Sets
Output Functional Computational Structures
Deterministic Process Logic Is Elementary
Faster Canonical Forms for Strongly Regular Graphs
A Fast Algorithm for Optimally Increasing the Edge-Connectivity
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
The Minimum Formula Size Problem is (ETH) Hard
Product Range Spaces, Sensitive Sampling, and Derandomization
Amplification of Probabilistic Boolean Formulas
Nearly Maximum Flows in Nearly Linear Time
Computing on a Free Tree via Complexity-Preserving Mappings
A census of finite automata (extended summary)
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, November 3-5, 1993
Efficient Computation of Continuous Skeletons
What is in #P and what is not?
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Explicit Unique-Neighbor Expanders
No Feasible Interpolation for TC0-Frege Proofs
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract)
Alternating Pushdown Automata (Preliminary Report)
Controllability, Recognizability, and Complexity Issues in Robot Motion Planning
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing
Time-Space Tradeoffs for Branching Programs
Exact Learning via the Monotone Theory (Extended Abstract)
Pair Algebra and Its Application
Lexicographic Products and the Power of Non-linear Network Coding
Multiplicative complexity of polynomial multiplication over finite fields (Extended abstract)
Sequential-machine realization using feedback shift registers
A Fast Planar Partition Algorithm, I (Extended Abstract)
The Moser-Tardos Framework with Partial Resampling
Procedures for minimization of "exclusive-OR" and "logical-equivalence" switching circuits
Algorithms for Quantum Computation: Discrete Logarithms and Factoring
Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)
The algebra of Boolean formulas: Some criteria for minimality
New Limits to Classical and Quantum Instance Compression
Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract)
Computation Times for Finite Groups, Semigroups and Automata
Stable Maintenance of Point Set Triangulations in Two Dimensions
Commutativity in the Algorithmic Lovász Local Lemma
Nearly Tight Low Stretch Spanning Trees
Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Algorithms for the ferromagnetic Potts model on expanders
Incomparability in Parallel Computation
Several Results in Program Size Complexity
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users
N-Process Synchronization by 4 log _2 N-Valued Shared Variables
On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report)
Parallelizing Elimination Orders with Linear Fill
Which Problems Have Strongly Exponential Complexity?
How to Compute in the Presence of Leakage
Marked Ancestor Problems
Forcing circuitry-Sequential building blocks for logical design
Dynamic Optimality - Almost
The Parking Permit Problem
Some Polynomial and Toeplitz Matrix Computations
On Pigeonhole Principles and Ramsey in TFNP
Combinational Complexity of Some Monotone Functions
Low-Dimensional Linear Programming with Violations
On the Complexity of Computing the Homology Type of a Triangulation
Sequential circuit synthesis using input delays
Iterative Procedures
Fully Dynamic Transitive Closure: Breaking Through the O(n 2 ) Barrier
Optimal myopic algorithms for random 3-SAT
Randomized Routing on Fat-Trees (Preliminary Version)
A Dichotomy Theorem for Constraints on a Three-Element Set
Upper and Lower Bounds for First Order Expressibility
The Monotone Complexity of k-clique on Random Graphs
An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract)
Finite-Memory Automata (Extended Abstract)
On the Size of Sets of Computable Functions
Reconstructing Strings from Substrings in Rounds
Subquadratic Simulations of Circuits by Branching Programs
Tight Lower Bounds for 2-query LCCs over Finite Fields
Sketching and Streaming Entropy via Approximation Theory
On the Complexity of Unique Solutions
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
Extractors and Rank Extractors for Polynomial Sources
Lower Bounds for Constant Depth Circuits in the Presence of Help Bits
Sparse Partitions (Extended Abstract)
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
Common Information and Unique Disjointness
Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
The Analysis of Hashing Algorithms that Exhibit k-ary Clustering
A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract)
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Boosting and Differential Privacy
Information Bounds Are Good for Search Problems on Ordered Data Structures
Iterative Row Sampling
Constant-Time Approximation Algorithms via Local Improvements
Unanimity in an Unknown and Unreliable Environment
Decomposition of Group Functions and the Synthesis of Multirail Cascades
Boolean Matrix Multiplication and Transitive Closure
Stochastic Load Balancing and Related Problems
Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract)
Deterministic Divisibility Testing via Shifted Partial Derivatives
Learning Probabilistic Prediction Functions (Extended Abstract)
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits
Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes
An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract)
An O(n^2.5) Algorithm for Maximum Matching in General Graphs
A Lower Bound for the Monotone Depth of Connectivity
Privacy and Communication Complexity
Smooth Histograms for Sliding Windows
Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
Logical design theory of NOR gate networks with no complemented inputs
On Random Symmetric Travelling Salesman Problems
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
The geometry of graphs and some of its algorithmic applications
On the Complexity of Matrix Group Problems I
On the (non)Universality of the One-Time Pad
IP=PSPACE
Splitters and Near-Optimal Derandomization
Decomposing Coverings and the Planar Sensor Cover Problem
Planar Disjoint Paths, Treewidth, and Kernels
Learning Mixtures of Gaussians
Minimal linear decompositions of switching functions
The Complexity of Tree Automata and Logics of Programs (Extended Abstract)
A Faster Deterministic Algorithm for Minimum Spanning Trees
On the Computational Complexity of Finding the Maxima of a Set of Vectors
Finding the k Shortest Paths
A New Probability Inequality Using Typical Moments and Concentration Results
Topology Matters in Communication
Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization
Parallel Complexity of Logical Query Programs
A Practical Scheme for Non-interactive Verifiable Secret Sharing
An integrated approach to automated computer maintenance
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
The NC Equivalence of Planar Integer Linear Programming and Euclidean GCD
Extractors for Circuit Sources
Dynamic Connectivity: Connecting to Networks and Geometry
The Universal Logic Block (ULB) and its Application to Logic Design
Randomness in Interactive Proofs
A Complexity Theory for Unbounded Fan-In Parallelism
Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract)
How to Allocate Tasks Asynchronously
The Computational Hardness of Estimating Edit Distance [Extended Abstract]
Learning and Smoothed Analysis
Research and algorithms in the theory of Boolean formulas
Universal Connecting Networks and the Synthesis of Canonical Sequential Circuits
Three Theorems Regarding Testing Graph Properties
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Pseudorandom Functions Revisited: The Cascade Construction and Its Concrete Security
Online Scheduling to Minimize Average Stretch
A Framework for Cost-scaling Algorithms for Submodular Flow Problems
Mixing Time Power Laws at Criticality
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
Random Evolution in Massive Graphs
Data Types (Extended Abstract)
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
Optimal Document Exchange and New Codes for Insertions and Deletions
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths
The Power of Sum-of-Squares for Detecting Hidden Structures
Constructive Algorithms for Discrepancy Minimization
Checking Automata and One-Way Stack Languages (Extended Abstract)
Graph Bisection Algorithms with Good Average Case Behavior
Space-Efficient Identity Based Encryption Without Pairings
The Complexity of Online Memory Checking
Abstract Combinatorial Programs and Efficient Property Testers
Sequential and Parallel Algorithms for Mixed Packing and Covering
The integrative properties of neurons
A Non-linear Lower Bound for Planar Epsilon-Nets
Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications
A Tree-Partitioning Technique with Applications to Expression Evaluation and Term Matching (Extended Abstract)
Nearly Optimal Expected-Case Planar Point Location
Obfuscating Compute-and-Compare Programs under LWE
Locally Testing Direct Product in the Low Error Range
Optimizing Synchronous Systems
7th Annual Symposium on Switching and Automata Theory, Berkeley, California, USA, October 23-25, 1966
Recognizing Circle Graphs in Polynomial Time
Randomized Search Trees
On the robustness of functional equations
Group-theoretic Algorithms for Matrix Multiplication
Minimization and Convexity in Threshold Logic
On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences
Smoothed Analysis in Unsupervised Learning via Decoupling
Reasoning about Infinite Computation Paths (Extended Abstract)
A realization procedure for threshold gate networks
Equivalence of Programs with Structured Variables
Universality and Tolerance
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs
Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity
On the Range Avoidance Problem for Circuits
Laconic Conditional Disclosure of Secrets and Applications
Clique Is Hard on Average for Unary Sherali-Adams
Constructive Discrepancy Minimization by Walking on the Edges
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Some Theorems about Matrix Multiplication (Extended Abstract)
IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011
Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions
Assignment Commands and Array Structures
Initial Algebra Semantics
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
Time-Space Tradeoffs for Branching Programs Contrasted with those for Straight-Line Programs
Non-Canonical Parsing
Separations in Communication Complexity Using Cheat Sheets and Information Complexity
Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)
How to Share Memory in a Distributed System (A Preliminary Version)
Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems
Techniques for Solving Graph Problems in Parallel Environments
Hardness of Approximate Hypergraph Coloring
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat
Why Certain Subgraph Computations Require Only Linear Time
Low-Degree Hardness of Random Optimization Problems
Tree Structures for Partial Match Retrieval
Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
The Synthesis of Multipurpose Logic Devices
Dynamic Maintenance of Geometric Structures Made Easy
Optimal Compression of Approximate Inner Products and Dimension Reduction
Concurrent Reading While Writing II: The Multi-writer Case
46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, Pittsburgh, PA, USA, October 23-25, 2005, Proceedings
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
Efficient Algorithms for Dynamic Allocation of Distributed Memory
Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds
Dynamic and Non-uniform Pricing Strategies for Revenue Maximization
Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design
Synchronization and Computing Capabilities of Linear Asynchronous Structures
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
Quantifying Knowledge Complexity
Near-Optimal Massively Parallel Graph Connectivity
The Average-Case Analysis of Some On-Line Algorithms for Bin Packing
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Symmetry Breaking in Distributive Networks
An Approximation Scheme for Planar Graph TSP
A Comparative Study of Models of Parallel Computation
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
New Data Structures for Orthogonal Range Searching
Pattern-Avoiding Access in Binary Search Trees
Memory Bounds for Continual Learning
Fast Uniform Generation of Random Graphs with Given Degree Sequences
Three Theorems on Polynomial Degrees of NP-Sets
Zero-knowledge with Log-Space Verifiers
On Allocating Goods to Maximize Fairness
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows
Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Secret Linear Congruential Generators Are Not Cryptographically Secure
On the Complexity of SAT
ABE for Circuits with poly (λ) -sized Keys from LWE
Garbled Protocols and Two-Round MPC from Bilinear Maps
Sparse Submodular Function Minimization
Hardness of Approximating the Minimum Distance of a Linear Code
Exact and Approximate Pattern Matching in the Streaming Model
On some transformation theorems in many-valued logical systems
Towards Strong Reverse Minkowski-Type Inequalities for Lattices
Maximizing Non-Linear Concave Functions in Fixed Dimension
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
Induced Cycles and Paths Are Harder Than You Think
Protocols for Secure Computations (Extended Abstract)
Towards Optimal Separations between Quantum and Randomized Query Complexities
The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract)
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time
Storing a Dynamic Sparse Table
An Improved Algorithm for Computing With Equations
Transforming Static Data Structures to Dynamic Structures (Abridged Version)
Irreducibility Testing and Factorization of Polynomials (Extended Abstract)
Improved approximation algorithms for multidimensional bin packing problems
Semantics of Probabilistic Programs
17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976
NP-Hardness of Learning Programs and Partial MCSP
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
Classical Verification of Quantum Computations in Linear Time
Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach
Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping
Lower Bounds for Matrix Product
An Efficient Parallel Algorithm for Planarity
From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique
Two Results on One-Way Stack Automata
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
Synthesis of switching circuits to yield prescribed probability relations
Two-level threshold minimization
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
The Parallel Complexity of the Abelian Permutation Group Membership Problem
High-Dimensional Geometric Streaming in Polynomial Space
Algebraic Cell Decomposition in NC (Preliminary Version)
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
Fast Multivariate Multipoint Evaluation Over All Finite Fields
On Newton's Method for Polynomials
14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973
A parallel algorithmic version of the Local Lemma