Algorithms

Publikation

Publikationer pr. år 2012 2013 2014 2015 2016 2017 2018 2019 2020 2022 2023 2024

• 129 Konferencebidrag i proceedings
• 55 Tidsskriftartikel
• 11 Konferenceartikel
• 7 Ph.d.-afhandling
• 30 Mere
  • 4 Paper
  • 4 Preprint
  • 3 Encyclopædiartikel
  • 2 Antologi
  • 2 Rapport
  • 2 Bidrag til bog/antologi
  • 2 Konferenceabstrakt til konference
  • 2 Bidrag til avis - Kronik
  • 2 Bidrag til avis - Avisartikel
  • 1 Forord/efterskrift
  • 1 Poster
  • 1 Bidrag til avis - Kommentar/debat
  • 1 Udgivelser på nettet - Net-publikation
  • 1 Andet bidrag
  • 1 Patent
  • 1 Working paper

Publikationer pr. år

Publikationer pr. år

Søgeresultater

• 2024

  An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio

  Jacob, R. & Goswami, M., 24 jan. 2024, I: Leibniz International Proceedings in Informatics (LIPIcs). 287, s. 1-17 17 s.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Konferenceartikel › Forskning

  Åben adgang

  • Bichromatic 100%
  • Competitive Ratio 100%
  • Worst-case Performance 20%
  • Randomized Algorithms 20%
  • Sorting Algorithm 20%

• 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, s. 1854 - 1871

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

  • Homomorphism 100%
  • Linear Combination 100%
  • CI-graph 100%
  • #P-hardness 100%
  • Polynomial Time 60%

• 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, s. 1-29.

  Publikation: Working paper › Preprint

  Fil

  • Causal Graph 100%
  • Causal Variables 40%
  • Completeness Theorem 20%
  • Faithfulness Constraint 20%
  • Markov Condition 20%

• Fairness Through Controlled (Un)Awareness in Node Embeddings

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

  Publikation: Working paper › Preprint

  Åben adgang

  Fil

  • Node Embedding 100%
  • Detectability 100%
  • Graph Embedding 100%
  • Representation Learning 100%
  • Hyperparameter Tuning 50%

• 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, s. 168 - 178 11 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning

  Åben adgang

  • Sorted Matrices 100%
  • Feasibility Trial 100%
  • Iterated Logarithm 100%
  • Recursive Method 100%
  • Shor 100%

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

  Jacob, R. & Goswami, M., aug. 2024, I: Leibniz International Proceedings in Informatics (LIPIcs). 317, s. 1-23 23 s.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Konferenceartikel › Forskning › peer review

  Åben adgang

  • Optimal Algorithm 100%
  • Instance Optimal 100%
  • Optimality 100%
  • Competitive Ratio 100%
  • Cost Function 100%

• Solving Polynomial Equations Over Finite Fields

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

  Publikation: Working paper › Preprint

  Fil

  • Equations over Finite Fields 100%
  • Solving Polynomial Equations 100%
  • Finite Field 100%
  • System of Equations 66%
  • Polynomial Equations 66%
• 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, s. 290-303 13 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Tight 100%
  • Quasi-polynomial 100%
  • Polynomial Bounds 100%
  • Hedging 100%
  • Min-cut 100%

• b-Coloring Parameterized by Clique-Width

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • B-coloring 100%
  • Clique-width 100%
  • Polynomial Time 50%
  • Tight 33%
  • Polynomial-time Algorithm 33%

• 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, s. 79-88

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

  • Differentially Private 100%
  • Heavy Hitters 100%
  • Approximates 100%
  • Histogram 100%
  • Differential Privacy 100%

• 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, Bind 282. s. 1-23 (Leibniz International Proceedings in Informatics (LIPIcs), Bind 282).

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

• 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, s. 3229 - 3244

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

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

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Planar Graph 100%
  • Bounded Degree 100%
  • Maximum number of Edges 100%
  • Matching number 100%
  • Maximum Degree 50%

• Optimal Parallel Sorting with Comparison Errors

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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Parallel Sorting 100%
  • Dislocation 100%
  • Comparison Errors 100%
  • Probability Theory 100%
  • Non-persistent 80%

• Overview of the SISAP 2023 Indexing Challenge

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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

• Recent Approaches and Trends in Approximate Nearest Neighbor Search

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning

  Åben adgang

  • Recent Advances 100%
  • Recent Trends 100%
  • Approximate Nearest Neighbor Search 100%
  • Nearest Neighbor Search 100%
  • Recent Approaches 100%

• Reducing the vertex cover number via edge contractions

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

• Solving k-Closest Pairs in High-Dimensional Data

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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

• 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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• 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.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

• 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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• Using edge contractions to reduce the semitotal domination number

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Edge Contraction 100%
  • Semitotal Domination number 100%
  • Edge 100%
  • Complexity Dichotomy 33%
  • K-edge 33%
• 2022

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

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • #SAT 100%
  • #Sat 100%
  • Constant-depth Circuits 100%
  • Degree Polynomial 100%
  • Randomized Algorithms 50%

• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Efficient Algorithm 100%
  • Subgraphs 100%
  • Sampling Algorithm 100%
  • Uniform Random 100%
  • Oracle 100%

• 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. Bind 151. s. 3108-3137

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• Determinants from Homomorphisms

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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• Fragile complexity of adaptive algorithms

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Fil

  • Adaptive Algorithm 100%
  • Fragile Complexity 100%
  • Minimum Element 50%
  • Log-log 25%
  • Algorithm Complexity 12%

• Graph Square Roots of Small Distance from Degree One Graphs

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Square Root 100%
  • Small Distance 100%
  • Graph Square Root 100%
  • Maximum Degree 50%
  • Graph Classes 50%

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

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Rådgivning › peer review

  Fil

  • Algebraic Circuits 100%
  • Constant Depth 100%
  • Arithmetic Operation 100%
  • Algorithm Designer 100%
  • Polynomial 100%

• Implementing Distributed Approximate Similarity Joins using Locality Sensitive Hashing

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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Locality Sensitive Hashing 100%
  • Approximate Similarity Join 100%
  • Distributed Settings 20%
  • Practice Theory 20%
  • Data Independence 20%

• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs

  Dell, H., Lapinskas, J. & Meeks, K., 7 nov. 2022, 92 s.

  Publikation: Working paper › Preprint

  Fil

  • Edge Evaluation 100%
  • Nearly Optimal 100%
  • Edge 100%
  • Model of Computation 100%
  • Worst Case 33%

• 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, s. 610-625

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Fil

• 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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Rainbow 100%
  • Path Graph 100%
  • Rainbow Vertex Coloring 100%
  • Diametral Path 100%
  • Induced Subgraph 100%

• 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, I: Algorithmica.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Bounded Degree 100%
  • Chordal Graph 100%
  • Maximum number of Edges 100%
  • Matching number 100%
  • Edge 100%

• 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, s. 32:1--32:23 23 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Multilinear Polynomial 100%
  • Partial Derivative Method 100%
  • Polynomial 100%
  • Partial Derivative 100%
  • Set-multilinear Formulas 75%

• 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, Bind 250.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• 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, s. 297-307

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

• Planar Graph Isomorphism Is in Log-Space

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Planar Graph 100%
  • Graph Isomorphism 100%
  • Log-space 100%
  • Lower and upper bounds 66%
  • Computational Problem 33%

• 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).

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

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

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Fast Access 100%
  • Differential Privacy 100%
  • Access to Space 100%
  • Low Error 100%
  • Optimal Spaces 100%

• 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. Bind 176. s. 177-189

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Approximate Nearest Neighbor Search 100%
  • Billion-scale 100%
  • Neighbour Search 100%
  • Computer Hardware 100%
  • Specialized Hardware 50%

• 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, I: ACM Transactions on Database Systems. 47, 1, s. 1-40 40 s., 4.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Similarity Search 100%
  • Nearest Neighbor 100%
  • High Dimension 100%
  • Data Structure 100%
  • Locality Sensitive Hashing 66%

• Sampling near neighbors in search for fairness

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Locality Sensitive Hashing 100%
  • Nearest Neighbor 100%
  • Nearest Neighbor Problem 100%
  • Data Structure 100%
  • Similarity Search 50%

• 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. s. 416-425

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

• Universal Sorting: Finding a DAG using Priced Comparisons

  Jacob, R. & Goswami, M., 8 nov. 2022, 40 s.

  Publikation: Bog / Antologi / Rapport / Ph.D.-afhandling › Rapport › Forskning

  Åben adgang

  • Competitive Ratio 100%
  • Bichromatic 75%
  • Sorting Task 50%
  • Randomized Algorithms 25%
  • Optimal Algorithm 25%

• Well-partitioned chordal graphs

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

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  Fil

  • Well-partitioned Chordal Graph 100%
  • Polynomial Time 100%
  • Clique 75%
  • Edge 50%
  • Vertex Set 37%

• 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).

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Linear Structure 100%
  • Parameterized Problems 100%
  • Dominating Set 100%
  • Capacitated 50%
  • Natural Places 50%
• 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, s. 1770 14 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

  • Complexity Dichotomy 100%
  • Immanants 100%
  • Polynomial Time 100%
  • Algebraic Complexity 25%
  • Computable 25%

• 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, s. 2141-2153 13 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

  • Butterfly Network 100%
  • Non-atomic 100%
  • Fork-Join Model 100%
  • Memory Access 100%
  • Join Operation 100%