Publication:
The bradley-terry condition is L-1-testable

Simple item page
dc.contributor.coauthorGeorgakopoulos, Agelos
dc.contributor.departmentDepartment of Mathematics
dc.contributor.kuauthorTyros, Konstantinos
dc.contributor.schoolcollegeinstituteCollege of Sciences
dc.date.accessioned2024-11-09T23:44:37Z
dc.date.issued2018
dc.description.abstractWe provide an algorithm with constant running time that given a weighted tournament T, distinguishes with high probability of success between the cases that T can be represented by a Bradley-Terry model, or cannot even be approximated by one. The same algorithm tests whether the corresponding Markov chain is reversible.
dc.description.indexedbyWOS
dc.description.indexedbyScopus
dc.description.issue4
dc.description.openaccessYES
dc.description.publisherscopeInternational
dc.description.sponsoredbyTubitakEuN/A
dc.description.sponsorshipEPSRC [EP/L002787/1]
dc.description.sponsorshipEuropean Research Council (ERC) under the European Union's Horizon research and innovation programme [639046]
dc.description.sponsorshipERC [306493]
dc.description.sponsorshipEPSRC [EP/L002787/1] Funding Source: UKRI
dc.description.sponsorshipEngineering and Physical Sciences Research Council [EP/L002787/1] Funding Source: researchfish The authors would like to thank Oded Goldreich for several suggestions. First author was supported by EPSRC grant EP/L002787/1, and by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 639046). Second author was supported by ERC grant 306493.
dc.description.volume341
dc.identifier.doi10.1016/j.disc.2017.10.026
dc.identifier.eissn1872-681X
dc.identifier.issn0012-365X
dc.identifier.quartileQ2
dc.identifier.scopus2-s2.0-85034822588
dc.identifier.urihttps://doi.org/10.1016/j.disc.2017.10.026
dc.identifier.urihttps://hdl.handle.net/20.500.14288/13674
dc.identifier.wos427664600038
dc.keywordsBradley-terry model
dc.keywordsProperty testing
dc.keywordsL-1-tester
dc.keywordsReversible markov Chain
dc.keywordsStochastic tournament property
dc.language.isoeng
dc.publisherElsevier Science Bv
dc.relation.ispartofDiscrete Mathematics
dc.subjectMathematics
dc.titleThe bradley-terry condition is L-1-testable
dc.typeJournal Article
dspace.entity.typePublication
local.contributor.kuauthorTyros, Konstantinos
local.publication.orgunit1College of Sciences
local.publication.orgunit2Department of Mathematics
relation.isOrgUnitOfPublication2159b841-6c2d-4f54-b1d4-b6ba86edfdbe
relation.isOrgUnitOfPublication.latestForDiscovery2159b841-6c2d-4f54-b1d4-b6ba86edfdbe
relation.isParentOrgUnitOfPublicationaf0395b0-7219-4165-a909-7016fa30932d
relation.isParentOrgUnitOfPublication.latestForDiscoveryaf0395b0-7219-4165-a909-7016fa30932d

Files

Collections

Publications without Fulltext