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 n^{0.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 |