Algorithms

2024

An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio

Jacob, R. & Goswami, M., 24 Jan 2024, In: Leibniz International Proceedings in Informatics (LIPIcs). 287, p. 1-17 17 p.

Research output: Journal Article or Conference Article in Journal › Conference article › Research

Open Access

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

Factored space models: Towards causality between levels of abstraction

Garrabrant, S., Mayer, M. G., Wache, M., Lang, L., Eisenstat, S. & Dell, H., 3 Dec 2024, p. 1-29.

Research output: Working paper › Preprint

File

Fairness Through Controlled (Un)Awareness in Node Embeddings

Vetter, D., Forth, J., Roig, G. & Dell, H., 29 Jul 2024, arXiv, p. 1-8, 8 p.

Research output: Working paper › Preprint

Open Access

File

Finding the saddlepoint faster than sorting

Jacob, R., Dallant, J., Haagensen, F., Kozma, L. & Wild, S., 2024, 2024 Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, p. 168 - 178 11 p.

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

Open Access

On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting

Jacob, R. & Goswami, M., Aug 2024, In: Leibniz International Proceedings in Informatics (LIPIcs). 317, p. 1-23 23 p.

Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

Open Access

Solving Polynomial Equations Over Finite Fields

Dell, H., Haak, A., Kallmayer, M. & Wennmann, L., 26 Oct 2024, arXiv, p. 1-25, 25 p.

Research output: Working paper › Preprint

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

b-Coloring Parameterized by Clique-Width

Jaffke, L., Thomé de Lima, P. & Lokshtanov, D., 23 Sept 2023, In: Theory of Computing Systems.

Research output: Journal Article or Conference Article in Journal › Journal article › 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

On the maximum number of edges in planar graphs of bounded degree and matching number

Thomé de Lima, P. & Jaffke, L., 2023, In: Discrete Mathematics. 346, 8

Research output: Journal Article or Conference Article in Journal › Journal article › 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

Recent Approaches and Trends in Approximate Nearest Neighbor Search

Aumüller, M. & Ceccarello, M., 2023, In: {IEEE} Data Engineering Bulletin.

Research output: Journal Article or Conference Article in Journal › Journal article › Research

Open Access

Reducing the vertex cover number via edge contractions

Thomé de Lima, P., dos Santos, V., Sau, I., Souza, U. & Tale, P., 2023, In: Journal of Computer and System Sciences. 136, p. 63-87 25 p.

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

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

Using edge contractions to reduce the semitotal domination number

Galby, E., Thomé de Lima, P., Mann, F. & Ries, B., 2023, In: Theoretical Computer Science. 939

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

2022

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Balaji, S., Krishan, V., Kush, D., Limaye, N. & Srinivasan, S., 2022, In: Algorithmica. 84

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

Dell, H., Lapinskas, J. & Meeks, K., 5 Jul 2022, In: S I A M Journal on Computing. 51, 4, p. 849-899

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

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

Fragile complexity of adaptive algorithms

Jacob, R., Fagerberg, R., Bose, P., Cano, P., Iacono, J. & Langerman, S., 5 Jun 2022, In: Theoretical Computer Science. 915, p. 92-102 11 p.

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

File

Graph Square Roots of Small Distance from Degree One Graphs

Golovach, P., Thomé de Lima, P. & Papadopoulos, C., 2022, In: Theory of Computing Systems. 66, p. 821-846

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.

Limaye, N., Srinivasan, S. & Tavenas, S., 2022, In: SIGACT News. 53, 3

Research output: Journal Article or Conference Article in Journal › Journal article › Commissioned › peer-review

File

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

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

Dell, H., Lapinskas, J. & Meeks, K., 7 Nov 2022, 92 p.

Research output: Working paper › Preprint

File

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 Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

Blair, J., Heggernes, P., Thomé de Lima, P. & Lokshtanov, D., 2022, In: Algorithmica.

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

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

Planar Graph Isomorphism Is in Log-Space

Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T. & Wagner, F., 2022, In: ACM Transactions on Computation Theory. 14, 2, p. 1-33 33 p.

Research output: Journal Article or Conference Article in Journal › Journal article › 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

Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access

Aumüller, M., Lebeda, C. J. & Pagh, R., 2022, In: Journal of Privacy and Confidentiality. 12, 2

Research output: Journal Article or Conference Article in Journal › Journal article › 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

Sampling a Near Neighbor in High Dimensions — Who is the Fairest of Them All?

Aumüller, M., Pagh, R., Silvestri, F., Har-Peled, S. & Mahabadi, S., 2022, In: ACM Transactions on Database Systems. 47, 1, p. 1-40 40 p., 4.

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

Sampling near neighbors in search for fairness

Aumüller, M., Har-Peled, S., Mahabadi, S., Pagh, R. & Silvestri, F., 2022, In: Communications of the A C M. 65, 8, p. 83-90

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

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

Universal Sorting: Finding a DAG using Priced Comparisons

Jacob, R. & Goswami, M., 8 Nov 2022, 40 p.

Research output: Book / Anthology / Report / Ph.D. thesis › Report › Research

Open Access

Well-partitioned chordal graphs

Ahn, J., Jaffke, L., Kwon, O.-J. & Thomé de Lima, P., 2022, In: Discrete Mathematics. 23 p., 112985.

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Open Access

File

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

Algorithms

Research output

Search results