|
Statistical Randomized Encodings: A Complexity Theoretic View |
|
|
Tighter Fourier Transform Lower Bounds |
|
|
Quantifying Competitiveness in Paging with Locality of Reference |
|
|
Approximation Algorithms for Computing Maximin Share Allocations |
|
|
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare |
|
|
Batched Point Location in SINR Diagrams via Algebraic Tools |
|
|
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-uniform Costs |
|
|
Serving in the Dark Should Be Done Non-uniformly |
|
|
Finding the Median (Obliviously) with Bounded Space |
|
|
Approximation Algorithms for Min-Sum k-Clustering |
|
|
Solving Linear Programming with Constraints Unknown |
|
|
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources |
|
|
Limitations of Algebraic Approaches to Graph Isomorphism Testing |
|
|
Fully Dynamic Matching in Bipartite Graphs |
|
|
Feasible Interpolation for QBF Resolution Calculi |
|
|
Simultaneous Approximation of Constraint Satisfaction Problems |
|
|
Design of Dynamic Algorithms via Primal-Dual Method |
|
|
What Percentage of Programs Halt? |
|
|
The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems |
|
|
Spotting Trees with Few Leaves |
|
|
Constraint Satisfaction Problems over the Integers with Successor |
|
|
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits |
|
|
Algorithms and Complexity for Turaev-Viro Invariants |
|
|
Big Data on the Rise? ? Testing Monotonicity of Distributions |
|
|
Unit Interval Editing Is Fixed-Parameter Tractable |
|
|
Streaming Algorithms for Submodular Function Maximization |
|
|
Multilinear Pseudorandom Functions |
|
|
Zero-Fixing Extractors for Sub-Logarithmic Entropy |
|
|
Interactive Proofs with Approximately Commuting Provers |
|
|
Popular Matchings with Two-Sided Preferences and One-Sided Ties |
|
|
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity |
|
|
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols |
|
|
Scheduling Bidirectional Traffic on a Path |
|
|
On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace |
|
|
On Planar Boolean CSP |
|
|
On Temporal Graph Exploration |
|
|
Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation |
|
|
A (1+e)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs |
|
|
Lower Bounds for the Graph Homomorphism Problem |
|
|
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree |
|
|
Relative Discrepancy Does not Separate Information and Communication Complexity |
|
|
A Galois Connection for Valued Constraint Languages of Infinite Size |
|
|
Approximately Counting H Colourings Is #BIS-Hard |
|
|
Taylor Polynomial Estimator for Estimating Frequency Moments |
|
|
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria |
|
|
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets |
|
|
Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search |
|
|
Optimal Encodings for Range Top-k, Selection, and Min-Max |
|
|
2-Vertex Connectivity in Directed Graphs |
|
|
Ground State Connectivity of Local Hamiltonians |
|
|
Uniform Kernelization Complexity of Hitting Forbidden Minors |
|
|
Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
|
|
Approximately Counting Locally-Optimal Structures |
|
|
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs (Extended Abstract) |
|
|
Fast Algorithms for Diameter-Optimally Augmenting Paths |
|
|
Hollow Heaps |
|
|
Linear-Time List Recovery of High-Rate Expander Codes |
|
|
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time |
|
|
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs |
|
|
Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities |
|
|
Local Reductions |
|
|
Query Complexity in Expectation |
|
|
Near-Linear Query Complexity for Graph Inference |
|
|
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set |
|
|
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden |
|
|
Lower Bounds for Sums of Powers of Low Degree Univariates |
|
|
Approximating CSPs Using LP Relaxation |
|
|
Comparator Circuits over Finite Bounded Posets |
|
|
Algebraic Properties of Valued Constraint Satisfaction Problem |
|
|
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic |
|
|
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy |
|
|
Replacing Mark Bits with Randomness in Fibonacci Heaps |
|
|
A PTAS for the Weighted Unit Disk Cover Problem |
|
|
Approximating the Expected Values for Combinatorial Optimization Problems Over Stochastic Points |
|
|
Deterministic Truncation of Linear Matroids |
|
|
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set |
|
|
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains |
|
|
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity |
|
|
A (2+e)-Approximation Algorithm for the Storage Allocation Problem |
|
|
Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas |
|
|
Computing the Frechet Distance Between Polygons with Holes |
|
|
An Improved Private Mechanism for Small Databases |
|
|
Binary Pattern Tile Set Synthesis Is NP-Hard |
|
|
Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity |
|
|
Condensed Unpredictability |
|
|
Sherali-Adams Relaxations for Valued CSPs |
|
|
Two-Sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm |
|
|
The Simultaneous Communication of Disjointness with Applications to Data Streams |
|
|
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication |
|
|
Statistical Randomized Encodings: A Complexity Theoretic View |
|
|
Tighter Fourier Transform Lower Bounds |
|
|
Quantifying Competitiveness in Paging with Locality of Reference |
|
図書
ＥＢ
