The proceedings contain 154 papers. The topics discussed include: an O(log log n)-approximation for submodular facility location;parameterized approximation for robust clustering in discrete geometric spaces;finer-gra...
ISBN:
(纸本)9783959773225
The proceedings contain 154 papers. The topics discussed include: an O(log log n)-approximation for submodular facility location;parameterized approximation for robust clustering in discrete geometric spaces;finer-grained reductions in fine-grained hardness of approximation;approximation schemes for geometric knapsack for packing spheres and fat objects;detecting disjoint shortest paths in linear time and more;the bit complexity of dynamic algebraic formulas and their determinants;approximate counting for spin systems in sub-quadratic time;from proof complexity to circuit complexity via interactive protocols;a multivariate to bivariate reduction for noncommutative rank and related results;list update with delays or time windows;sublinear algorithms for TSP via path covers;and random separating hyperplane theorem and learning polytopes.
The proceedings contain 133 papers. The topics discussed include: a (slightly) improved approximation algorithm for the metric traveling salesperson problem;an almost-linear time algorithm for maximum flow and more;co...
ISBN:
(纸本)9783959772785
The proceedings contain 133 papers. The topics discussed include: a (slightly) improved approximation algorithm for the metric traveling salesperson problem;an almost-linear time algorithm for maximum flow and more;context-bounded analysis of concurrent programs;quantum codes, local testability and interactive proofs: state of the art and open questions;optimal decremental connectivity in non-sparse graphs;stable matching: choosing which proposals to make;expander decomposition with fewer inter-cluster edges using a spectral cut player;locality in online, dynamic, sequential, and distributed graph algorithms;an efficient algorithm for all-pairs bounded edge connectivity;low-depth arithmetic circuit lower bounds: bypassing set-multilinearization;multi-layer peeling for linear arrangement and hierarchical clustering;improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions;and cumulative memory lower bounds for randomized and quantum computation.
The proceedings contain 132 papers. The topics discussed include: improved approximation algorithms and lower bounds for search-diversification problems;round-optimal lattice-based threshold signatures, revisited;para...
ISBN:
(纸本)9783959772358
The proceedings contain 132 papers. The topics discussed include: improved approximation algorithms and lower bounds for search-diversification problems;round-optimal lattice-based threshold signatures, revisited;parameterized sensitivity oracles and dynamic algorithms using exterior algebras;low-degree polynomials extract from local sources;decremental matching in general graphs;near-optimal algorithms for stochastic online bin packing;finding monotone patterns in sublinear time, adaptively;memoryless worker-task assignment with polylogarithmic switching cost;fully-dynamic graph sparsifiers against an adaptive adversary;fast sampling via spectral independence beyond bounded-degree graphs;deterministic sensitivity oracles for diameter, eccentricities and all pairs distances;and Hodge decomposition and general Laplacian solvers for embedded simplicial complexes.
The proceedings contain 142 papers. The topics discussed include: from verification to causality-based explications;symmetries and complexity;distributed subgraph finding: progress and challenges;error resilient space...
ISBN:
(纸本)9783959771955
The proceedings contain 142 papers. The topics discussed include: from verification to causality-based explications;symmetries and complexity;distributed subgraph finding: progress and challenges;error resilient space partitioning;fine-grained hardness for edit distance to a fixed sequence;local approximations of the independent set polynomial;an output-sensitive algorithm for computing the union of cubes and fat boxes in 3d;dynamic enumeration of similarity joins;faster algorithms for bounded tree edit distance;improved approximation for longest common subsequence over small alphabets;comparative design-choice analysis of color refinement algorithms beyond the worst case;search problems in trees with symmetries: near optimal traversal strategies for individualization-refinement algorithms;breaking the barrier of 2 for the competitiveness of longest queue drop;relaxed locally correctable codes with improved parameters;and optimal fine-grained hardness of approximation of linear equations.
The proceedings contain 146 papers. The topics discussed include: complexity-theoretic limitations on blind delegated quantum computation;faster algorithms for all-pairs bounded min-cuts;fine-grained reductions and qu...
ISBN:
(纸本)9783959771092
The proceedings contain 146 papers. The topics discussed include: complexity-theoretic limitations on blind delegated quantum computation;faster algorithms for all-pairs bounded min-cuts;fine-grained reductions and quantum speedups for dynamic programming;lower bounds for multiplication via network coding;deterministic combinatorial replacement paths and distance sensitivity oracles;algorithms and hardness for diameter in dynamic graphs;log diameter rounds algorithms for 2-vertex and 2-edge connectivity;two party distribution testing: communication and security;two new results about quantum exact learning;when algorithms for maximal independent set and maximal matching run in sublinear time;and capacitated dynamic programming: faster knapsack and graph algorithms.
暂无评论