onr:"swepub:oai:DiVA.org:mau-64600"
Sökning: onr:"swepub:oai:DiVA.org:mau-64600" > Pushing the Online ...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
- Gąsieniec, LeszekDepartment of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 38X, UK,University of Liverpool (författare)
Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases
- Artikel/kapitelEngelska2019
Förlag, utgivningsår, omfång ...
- 2019-04-09
- Cham :Springer,2019
- printrdacarrier
Nummerbeteckningar
- LIBRIS-ID:oai:DiVA.org:mau-64600
- https://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-64600URI
- https://doi.org/10.1007/978-3-030-18126-0_14DOI
- oai:portal.research.lu.se:publications/fc31a0f2-8539-4908-b28b-72e546e84bc3URI
Kompletterande språkuppgifter
- Språk:engelska
- Sammanfattning på:engelska
Ingår i deldatabas
- SwePubSwePub
Klassifikation
Anmärkningar
- Henzinger et al. posed the so called Online Boolean Matrix-vector Multiplication (OMv) conjecture and showed that it implies tight hardness results for several basic partially dynamic or dynamic problems [STOC’15].We show that the OMv conjecture is implied by a simple off-line conjecture. If a not uniform (i.e., it might be different for different matrices) polynomial-time preprocessing of the matrix in the OMv conjecture is allowed then we can show such a variant of the OMv conjecture to be equivalent to our off-line conjecture. On the other hand, we show that the OMV conjecture does not hold in the restricted cases when the rows of the matrix or the input vectors are clustered.
Ämnesord och genrebeteckningar
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- Boolean matrix
- Product of matrix and vector
- Dynamic graph problems
- Online computation
- Time complexity
Biuppslag (personer, institutioner, konferenser, titlar ...)
- Jansson, JesperDepartment of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong,Hong Kong Polytechnic University (författare)
- Levcopoulos, ChristosDepartment of Computer Science, Lund University, 22100, Lund, Sweden,Institutionen för datavetenskap (författare)
- Lingas, AndrzejDepartment of Computer Science, Lund University, 22100, Lund, Sweden,Institutionen för datavetenskap(Swepub:lu)09fd65c1-2d22-477b-8095-ab06351e9b6f (författare)
- Persson, MiaMalmö universitet,Institutionen för datavetenskap och medieteknik (DVMT),Malmö University(Swepub:mau)tsmipe (författare)
- Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 38X, UKUniversity of Liverpool (creator_code:org_t)
Sammanhörande titlar
- Ingår i:Frontiers in AlgorithmicsCham : Springer, s. 156-16997830301812539783030181260
Internetlänk
- https://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-64600
- https://doi.org/10.1007/978-3-030-18126-0_14
- oai:portal.research.lu.se:publications/fc31a0f2-8539-4908-b28b-72e546e84bc3
Hitta via bibliotek
- Frontiers in Algorithmics (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Gąsieniec, Lesze ...
- Jansson, Jesper
- Levcopoulos, Chr ...
- Lingas, Andrzej
- Persson, Mia
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- och Datavetenskap
- Artiklar i publikationen
- Frontiers in Alg ...
- Av lärosätet
- Malmö universitet
- Lunds universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst. Hantera kakor
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
