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.
[57] |
"Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability" 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 |
[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 |
[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 |