Algorithms

2024

Count on CFI graphs for #P-hardness

Curticapean, R.-C., 2024, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024. Society for Industrial and Applied Mathematics, p. 1854 - 1871

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

2023

A tight quasi-polynomial bound for Global Label Min-Cut

Jaffke, L., Thomé de Lima, P., Masařík, T., Pilipczuk, M. & Souza, U., 2023, Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, p. 290-303 13 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch

Lebeda, C. J. & Tětek, J., 18 Jun 2023, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023. New York: Association for Computing Machinery, p. 79-88

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Correlated-Output Differential Privacy and Applications to Dark Pools

Hsin-yu Chiang, J., David, B., Gama, M. & Lebeda, C. J., 2023, 5th Conference on Advances in Financial Technologies (AFT 2023) . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Vol. 282. p. 1-23 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 282).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Hatzel, M., Jaffke, L., Thomé de Lima, P., Masařík, T., Pilipczuk, M., Sharma, R. & Sorge, M., 2023, Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, p. 3229 - 3244

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Optimal Parallel Sorting with Comparison Errors

Jacob, R. & Goodrich, M. T., 17 Jun 2023, Proceedings SPAA '23. Association for Computing Machinery, p. 355-365 11 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Overview of the SISAP 2023 Indexing Challenge

Aumüller, M., Chavez, E. & Tellez, E. S., 2023, Similarity Search and Applications, SISAP 2023.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Solving k-Closest Pairs in High-Dimensional Data

Aumüller, M. & Ceccarello, M., 2023, Similarity Search and Applications, SISAP 2023.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Structural Parameterizations of b-Coloring

Jaffke, L., Thomé de Lima, P. & Sharma, R., 2023, 34th International Symposium on Algorithms and Computation (ISAAC 2023). Dagstuhl Publishing, Germany

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Suitability of Nearest Neighbour Indexes for Multimedia Relevance Feedback

Aumüller, M., Khan, O. S. & Jónsson, B. T., 2023, Similarity Search and Applications SISAP 2023.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Treewidth is NP-complete on cubic graphs (and related results)

Bodlaender, H., Bonnet, É., Jaffke, L., Knop, D., Thomé de Lima, P., Milanič, M., Ordyniak, S., Pandey, S. & Suchý, O., 2023, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Dagstuhl Publishing, Germany

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

2022

DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search

Aumüller, M., Karppa, M. & Pagh, R., 2022, AISTATS 2022: International Conference on Artificial Intelligence and Statistics. Vol. 151. p. 3108-3137

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Determinants from Homomorphisms

Curticapean, R.-C., 2022, 30th Annual European Symposium on Algorithms (ESA 2022). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 38

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Implementing Distributed Approximate Similarity Joins using Locality Sensitive Hashing

Aumüller, M. & Ceccarello, M., 2022, EDBT: International Conference on Extending Database Technology. 13 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

On the Closures of Monotone Algebraic Classes and Variants of the Determinant

Chaugule, P. & Limaye, N., 2022, LATIN 2022: Theoretical Informatics - 15th Latin American Symposium. Springer Nature, p. 610-625

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

File

On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs

Dyrseth, J. & Thomé de Lima, P., 2022, 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Dagstuhl Publishing, Germany

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials.

Limaye, N., Srinivasan, S. & Tavenas, S., 2022, 37th Computational Complexity Conference, CCC 2022. Dagstuhl Publishing, Germany, p. 32:1--32:23 23 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

On the VNP-Hardness of Some Monomial Symmetric Polynomials

Curticapean, R.-C., Limaye, N. & Srinivasan, S., 14 Dec 2022, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Vol. 250.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Parameterizing the permanent: Hardness for fixed excluded minors

Curticapean, R.-C. & Xia, M., 2022, Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, p. 297-307

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Reducing the Vertex Cover Number via Edge Contractions

Thomé de Lima, P., dos Santos, V., Sau, I., Souza, U. & Tale, P., 2022, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor Search

Aumüller, M., Simhadri, H., Williams, G., Douze, M., Babenko, A., Baranchuk, D., Hosseini, L., Krishnaswamny, R., Srinivasa, G., Subramanya, S. J. & Wang, J., 2022, Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track. Vol. 176. p. 177-189

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.

Limaye, N., Srinivasan, S. & Tavenas, S., 2022, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing. p. 416-425

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Taming Graphs with No Large Creatures and Skinny Ladders

Gajarsky, J., Jaffke, L., Thomé de Lima, P., Novotná, J., Pilipczuk, M., Rzążewski, P. & Souza, U., 2022, Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022). Dagstuhl Publishing, Germany

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Bodlaender, H., Groenland, C., Jacob, H., Jaffke, L. & Thomé de Lima, P., 2022, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

2021

A full complexity dichotomy for immanant families

Curticapean, R.-C., 15 Jun 2021, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 1770 14 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model

Jacob, R., Sitchinava, N. & Goodrich, M. T., 14 Jan 2021, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, p. 2141-2153 13 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Computational Complexity of Computing a Quasi-Proper Equilibrium

Lund, T. B. & Hansen, K. A., 2021, Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham, p. 259-271 13 p. (Lecture Notes in Computer Science, Vol. 12867).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access

Aumüller, M., Pagh, R. & Lebeda, C. J., 2021, Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 14 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Efficient Differentially Private F0 Linear Sketching

Pagh, R. & Nielsen, N. M. S., 2021, 24th International Conference on Database Theory (ICDT 2021). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Fragile Complexity of Adaptive Algorithms

Jacob, R., Fagerberg, R., Bose, P., Cano, P., Iacono, J. & Langerman, S., 10 May 2021, International Conference on Algorithms and Complexity. Springer, Vol. LNCS 12701. p. 144-157 14 p. (LNCS, Vol. 12701).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Improved Differentially Private Euclidean Distance Approximation

Nielsen, N. M. S., Jun 2021, PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Interactions IX: Association of Computing Machinery ACM, Vol. 40. p. 42–56 56

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Curticapean, R.-C., Dell, H. & Husfeldt, T., 2021, Proceedings of the 29th Annual European Symposium on Algorithms. Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Vol. 204. 17 p. 34

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

2020

Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk)

Aumüller, M., 2020, 18th International Symposium on Experimental Algorithms (SEA 2020). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, p. 1:1–1:3 1. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Approximately counting and sampling small witnesses using a colourful decision oracle

Dell, H., Lapinskas, J. & Meeks, K., 2020, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Chawla, S. (ed.). Society for Industrial and Applied Mathematics, p. 2201-2211 11 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Composable Sketches for Functions of Frequencies: Beyond the Worst Case

Cohen, E., Geri, O. & Pagh, R., 2020, Proceedings of the 37 th International Conference on Machine Learning. ML Research Press

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Confirmation Sampling for Exact Nearest Neighbor Search

Christiani, T. L., Pagh, R. & Thorup, M., 2020, SISAP 2020: Similarity Search and Applications. Springer, p. 97-110 (Lecture Notes in Computer Science, Vol. 12440).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

DaNewsroom: A Large-scale Danish Summarisation Dataset

Varab, D. & Schluter, N., Apr 2020, Proceedings of the 12th Conference on Language Resources and Evaluation (LREC 2020). European Language Resources Association, p. 6731–6739

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Differentially Private Sketches for Jaccard Similarity Estimation

Aumüller, M., Bourgeat & Schmurr, 2020, International Conference on Similarity Search and Applications: SISAP 2020. Springer, p. 18-32 (Lecture Notest in Computer Science, Vol. 12440).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

File

Fair Near Neighbor Search: Independent Range Sampling in High Dimensions. PODS

Aumüller, M., Pagh, R. & Silvestri, F., 2020, PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, p. 191–204

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Oblivious Sketching of High-Degree Polynomial Kernels

Ahle, T. D., Kapralov, M., Knudsen, J. B. T., Pagh, R., Velingker, A., Woodruff, D. & Zandieh, A., 2020, SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, 20 p.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

On the I/O Complexity of the k-Nearest Neighbors Problem

Goswami, M., Jacob, R. & Pagh, R., Jun 2020, PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, p. 205-212 (ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Private Aggregation from Fewer Anonymous Messages

Ghazi, B., Manurangsi, P., Pagh, R. & Velingker, A., 2020, Advances in Cryptology – EUROCRYPT 2020. Springer, p. 798-827 (Lecture Notes in Computer Science, Vol. 12106).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead

Ghazi, B., Kumar, R., Manurangsi, P. & Pagh, R., 2020, Proceedings of the 37th International Conference on Machine Learning. ML Research Press

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Pure Differentially Private Summation from Anonymous Messages

Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., Pagh, R. & Velingker, A., 2020, 1st Conference on Information-Theoretic Cryptography (ITC 2020). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, p. 15:1–15:23 (Leibniz International Proceedings in Informatics, Vol. 163).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Reproducibility Companion Paper: Visual Sentiment Analysis for Review Images with Item-Oriented and User-Oriented CNN

Truong, Q.-T., Lauw, H. W., Aumüller, M. & Nitta, N., 2020, MM '20: Proceedings of the 28th ACM International Conference on Multimedia. Association for Computing Machinery, p. 4444-4447

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Running Experiments with Confidence and Sanity

Aumüller, M. & Ceccarello, M., 2020, International Conference on Similarity Search and Applications. Springer, p. 18-32

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

The space complexity of inner product filters

Pagh, R. & Sivertsen, J. V. T., 2020, 23rd International Conference on Database Theory (ICDT 2020). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, p. 22:1–22:14 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 155).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

WOR and p’s: Sketches for Lp-sampling Without Replacement

Cohen, E., Pagh, R. & Woodruff, D., 2020, 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Neural Information Processing Systems

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

2019

Benchmarking Nearest Neighbor Search: Influence of Local Intrinsic Dimensionality and Result Diversity in Real-World Datasets

Aumüller, M. & Ceccarello, M., 2019, EDML 2019 - Evaluation and Experimental Design in Data Mining and Machine Learning. CEUR Workshop Proceedings, Vol. 2436. (CEUR Workshop Proceedings, Vol. 2436).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Fragile Complexity of Comparison-Based Algorithms

Afshani, P., Fagerberg, R., Hammer, D. M. G., Jacob, R., Kostitsyna, I., Meyer, U., Penschuck, M. & Sitchinava, N., 9 Sept 2019, 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, p. 2:1–2:19 2. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Open Access

File

Algorithms

Research output

Search results