max planck institut
informatik
informatik
Copyright notice: The respective pre-print or author-prepared version of a paper is provided for timely communication among scholars, without permission for further distribution. The definitive version of a paper is the published version.
| [98] |
"Knapsack with Small Items in Near-Quadratic Time" STOC'24: Proc. of the 56th ACM Symposium on the Theory of Computing |
| [97] |
"Fine-Grained Complexity of Earth Mover's Distance under Translation" SoCG'24: Proc. of the 40th International Symposium on Computational Geometry Invited to JoCG special issue |
| [96] |
"The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds" ITCS'24: Proc. of the 15th Innovations in Theoretical Computer Science conference Invited to TheoretiCS |
| [95] |
"Faster Sublinear-Time Edit Distance" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [94] |
"Approximating Subset Sum Ratio faster than Subset Sum" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [93] |
"The Time Complexity of Fully Sparse Matrix Multiplication" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [92] |
"Dynamic Dynamic Time Warping" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [91] |
"Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!" FOCS'23: Proc. of the 64th Annual IEEE Symposium on Foundations of Computer Science |
| [90] |
"Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution" ESA'23: Proc. of the 31st Annual European Symposium on Algorithms |
| [89] |
"Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics" STOC'23: Proc. of the 55th ACM Symposium on the Theory of Computing Invited to SICOMP special issue |
| [88] |
"Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms" SODA'23: Proc. of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [87] |
"Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [86] |
"Improved Sublinear-Time Edit Distance for Preprocessed Strings" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [85] |
"A Structural Investigation of the Approximability of Polynomial-Time Problems" ICALP'22: Proc. of the 49th International Colloquium on Automata, Languages, and Programming |
| [84] |
"Tight Fine-Grained Bounds for Direct Access on Join Queries" PODS'22: Proc. of the 41st ACM Symposium on Principles of Database Systems |
| [83] |
"Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves" SoCG'22: Proc. of the 38th International Symposium on Computational Geometry |
| [82] |
"Towards sub-quadratic diameter computation in geometric intersection graphs" SoCG'22: Proc. of the 38th International Symposium on Computational Geometry |
| [81] |
"Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds" SoCG'22: Proc. of the 38th International Symposium on Computational Geometry |
| [80] |
STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing |
| [79] |
"Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime" STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing |
| [78] |
"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution" SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [77] |
"Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance" SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [76] |
"Fine-Grained Completeness for Optimization in P" APPROX-RANDOM'21: Proc. of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems |
| [75] |
"Fast n-fold Boolean Convolution via Additive Combinatorics" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming |
| [74] |
"Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming |
| [73] |
"A Linear-Time n0.4-Approximation for Longest Common Subsequence" ICALP'21: Proc. of the 48th International Colloquium on Automata, Languages, and Programming *Vincent Cohen-Addad is author of the extended Arxiv version, but not of the ICALP proceedings version. |
| [72] |
"Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution" STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing |
| [71] |
"Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation" SoCG'21: Proc. of the 37th International Symposium on Computational Geometry Invited to JoCG special issue |
| [70] |
"A Fine-Grained Perspective on Approximating Subset Sum and Partition" SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [69] |
"On Near-Linear-Time Algorithms for Dense Subset Sum" SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [68] |
"Fast and Simple Modular Subset Sum" SOSA@SODA'21: Proc. of the 4th SIAM Symposium on Simplicity in Algorithms |
| [67] |
"Impossibility Results for Grammar-Compressed Linear Algebra" NeurIPS'20: Proc. of the 34th Annual Conference on Neural Information Processing Systems |
| [66] |
ESA'20: Proc. of the 28th Annual European Symposium on Algorithms |
| [65] |
"Scheduling Lower Bounds via AND Subset Sum" ICALP'20: Proc. of the 47th International Colloquium on Automata, Languages, and Programming |
| [64] |
"Faster Minimization of Tardy Processing Time on a Single Machine" ICALP'20: Proc. of the 47th International Colloquium on Automata, Languages, and Programming |
| [63] |
"Top-k-Convolution and the Quest for Near-linear Output-sensitive Subset Sum" STOC'20: Proc. of the 52nd ACM Symposium on the Theory of Computing |
| [62] |
"On Geometric Set Cover for Orthants" ESA'19: Proc. of the 27th Annual European Symposium on Algorithms |
| [61] |
CCC'19: Proc. of the 34th Conference on Computational Complexity |
| [60] |
"Polyline Simplification has Cubic Complexity" SoCG'19: Proc. of the 35rd International Symposium on Computational Geometry Invited to JoCG special issue |
| [59] |
"Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance" SoCG'19: Proc. of the 35th International Symposium on Computational Geometry |
| [58] |
"Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max" STOC'19: Proc. of the 51st ACM Symposium on the Theory of Computing |
| [57] |
SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [56] |
"Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts" SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [55] |
"SETH-Based Lower Bounds for Subset Sum and Bicriteria Path" SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms Invited to HALG'20 and to TALG special issue |
| [54] |
"A PTAS for l_p-Low Rank Approximation" SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [53] |
"Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS" FSTTCS'18: Proc. of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
| [52] |
"Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth" IPEC'18: Proc. of the 13th International Symposium on Parameterized and Exact Computation Invited to Algorithmica special issue |
| [51] |
"Tighter Connections Between Formula-SAT and Shaving Logs" ICALP'18: Proc. of the 45th International Colloquium on Automata, Languages, and Programming |
| [50] |
"More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture" STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing |
| [49] |
STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing |
| [48] |
"Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)" SODA'18: Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [47] |
"Multivariate Fine-Grained Complexity of Longest Common Subsequence" SODA'18: Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [46] |
"Approximation Algorithms for l_0-Low Rank Approximation" NIPS'17: Proc. of the 31st Annual Conference on Neural Information Processing Systems |
| [45] |
"A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)" SIGSPATIAL'17: Proc. of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems Winner of ACM SIGSPATIAL Cup 2017 |
| [44] |
FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science |
| [43] |
"A Dichotomy for Regular Expression Membership Testing" FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science |
| [42] |
"A Note on Hardness of Diameter Approximation" (Brief Announcement) DISC'17: Proc. of the 31st International Symposium on Distributed Computing |
| [41] |
"Sampling Geometric Inhomogeneous Random Graphs in Linear Time" ESA'17: Proc. of the 25th Annual European Symposium on Algorithms |
| [40] |
"Greedy Routing and the Algorithmic Small-World Phenomenom" PODC'17: Proc. of the 36th ACM Symposium on Principles of Distributed Computing |
| [39] |
"On Algebraic Branching Programs of Small Width" CCC'17: Proc. of the 32th Conference on Computational Complexity |
| [38] |
"Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs" ICALP'17: Proc. of the 44th International Colloquium on Automata, Languages, and Programming |
| [37] |
"Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars" CPM'17: Proc. of the 28th Annual Symposium on Combinatorial Pattern Matching |
| [36] |
"Maximum Volume Subset Selection for Anchored Boxes" SoCG'17: Proc. of the 33rd International Symposium on Computational Geometry |
| [35] |
"A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum" SODA'17: Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [34] |
FOCS'16: Proc. of the 57th Annual IEEE Symposium on Foundations of Computer Science Invited to HALG'17 and to SICOMP special issue |
| [33] |
"Hitting Set for Hypergraphs of Low VC-dimension" ESA'16: Proc. of the 24th Annual European Symposium on Algorithms |
| [32] |
"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping" FOCS'15: Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science |
| [31] |
"Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds" ISAAC'15: Proc. of the 26th International Symposium on Algorithms and Computation Invited to IJCGA special issue |
| [30] |
"Ultra-Fast Load Balancing on Scale-Free Networks" ICALP'15: Proc. of the 42th International Colloquium on Automata, Languages, and Programming |
| [29] |
"Efficient Computation of Two-dimensional Solution Sets Maximizing the Epsilon-Indicator" CEC'15: Proc. of the 2015 IEEE Congress on Evolutionary Computation |
| [28] |
"Approximability of the Discrete Fréchet Distance" SoCG'15: Proc. of the 31st International Symposium on Computational Geometry |
| [27] |
"Parameterized Complexity Dichotomy for Steiner Multicut" STACS'15: Proc. of the 32nd Symposium on Theoretical Aspects of Computer Science |
| [26] |
FOCS'14: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science |
| [25] |
"De-anonymization of Heterogeneous Random Graphs in Quasilinear Time" ESA'14: Proc. of the 22nd Annual European Symposium on Algorithms |
| [24] |
"Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator" PPSN'14: Proc. of the 13th International Conference on Parallel Problem Solving from Nature |
| [23] |
"Internal DLA: Efficient Simulation of a Physical Growth Model" ICALP'14: Proc. of the 41th International Colloquium on Automata, Languages and Programming |
| [22] |
"Two-dimensional Subset Selection for Hypervolume and Epsilon-Indicator" GECCO'14: 16th Annual Conference on Genetic and Evolutionary Computation |
| [21] |
"Balls into bins via local search: cover time and maximum load" STACS'14: Proc. of the 31st Symposium on Theoretical Aspects of Computer Science |
| [20] |
"Counting Triangulations Approximately" CCCG'13: Proc. of the 25th Canadian Conference on Computational Geometry Invited to CGTA special issue |
| [19] |
"Bringing Order to Special Cases of Klee’s Measure Problem" MFCS'13: Proc. of the 38th International Symposium on Mathematical Foundations of Computer Science |
| [18] |
"Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems" MFCS'13: Proc. of the 38th International Symposium on Mathematical Foundations of Computer Science |
| [17] |
"Exact and Efficient Generation of Geometric Random Variates and Random Graphs" ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming |
| [16] | "Online Checkpointing with Improved Worst-Case Guarantees" ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming |
| [15] | "Minimizing maximum (weighted) flow-time on related and unrelated machines" ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming |
| [14] | "Parameterized Average-Case Complexity of the Hypervolume Indicator" GECCO'13: Proc. of the 15th Annual Conference on Genetic and Evolutionary Computation |
| [13] | "Succinct Sampling from Discrete Distributions" STOC'13: Proc. of the 45th ACM Symposium on the Theory of Computing |
| [12] | "Efficient Sampling Methods for Discrete Distributions" ICALP'12: Proc. of the 39th International Colloquium on Automata, Languages and Programming |
| [11] | "Convergence of Hypervolume-Based Archiving Algorithms II: Competitiveness" GECCO'12: Proc. of the 14th Annual Conference on Genetic and Evolutionary Computation |
| [10] | "Counting Crossing Free Structures" SoCG'12: Proc. of the 2012 Annual Symposium on Computational Geometry |
| [9] | "Approximation-Guided Evolutionary Multi-Objective Optimization" IJCAI'11: Proc. of the 22nd International Joint Conferences on Artificial Intelligence |
| [8] | "Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness" GECCO'11: Proc. of the 13th Annual Conference on Genetic and Evolutionary Computation |
| [7] | "The Logarithmic Hypervolume Indicator" FOGA'11: Proc. of the 11th ACM Foundations of Genetic Algorithms |
| [6] | "Klee's measure problem on fat boxes in time O(n(d+2)/3)" SoCG'10: Proc. of the 26th Annual Symposium on Computational Geometry Invited to CGTA special issue |
| [5] | "Tight Bounds for the Approximation Ratio of the Hypervolume Indicator" PPSN'10: Proc. of the 11th International Conference on Parallel Problem Solving From Nature |
| [4] | "The Maximum Hypervolume Set Yields Near-optimal Approximation" GECCO'10: Proc. of the 12th Annual Conference on Genetic and Evolutionary Computation Winner of best paper award |
| [3] | "Approximating the Least Hypervolume Contributor: NP-hard in General, but Fast in Practice" EMO'09: Proc. of the 5th International Conference on Evolutionary Multi-Criterion Optimization |
| [2] | "Don't be Greedy when Calculating Hypervolume Contributions" FOGA'09: Proc. of the 10th ACM Foundations of Genetic Algorithms |
| [1] | "Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects" ISAAC'08: Proc. of the 19th International Symposium on Algorithms and Computation |