ΑΙhub.org
 

Congratulations to the authors of the #IJCAI2022 distinguished papers


by
28 July 2022



share this:
IJCAI-ECAI 2022 logo

The IJCAI distinguished paper awards recognise some of the best papers presented at the conference each year. This year, three articles were named as distinguished papers. The winners were selected by the associate programme committee chairs, the programme and general chairs, and the president of EurAI.

And the winners are…

Plurality veto: A simple voting rule achieving optimal metric distortion
Fatih Kizilkaya, David Kempe

Abstract:
The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule’s purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality Veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k = 0) and Plurality Veto (for k = n – 1), and k controls the variance of the output. We show that for all k, this rule has expected distortion at most 3.

Read the paper in full here.


QCDCL with cube learning or pure literal elimination – what is best?
Benjamin Böhm, Tomas Peitl, Olaf Beyersdorff

Abstract:
Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of the QCDCL models are exponentially incomparable with respect to proof size (and hence solver running time), pointing towards different orthogonal ways how to practically implement QCDCL.

Read the paper in full here.


Completeness and diversity in depth-first proof-number search with applications to retrosynthesis
Christopher Franz, Georg Mogk, Thomas Mrziglod, Kevin Schewior

Abstract:
We revisit Depth-First Proof-Number Search (DFPN), a well-known algorithm for solving two-player games. First, we consider the completeness property of the algorithm and its variants, i.e., whether they always find a winning strategy when there exists one. While it is known that the standard version is not complete, we show that the combination with the simple Threshold Controlling Algorithm is complete, solving an open problem from the area. Second, we modify DFPN to compute a diverse set of solutions rather than just a single one. Finally, we apply this new variant in Chemistry to the synthesis planning of new target molecules (Retrosynthesis). In this domain a diverse set of many solutions is desirable. We apply additional modifications from the literature to the algorithm and show that it outperforms Monte-Carlo Tree-Search, another well-known algorithm for the same problem, according to a natural diversity measure.

Read the paper in full here.




tags: ,


Lucy Smith is Senior Managing Editor for AIhub.
Lucy Smith is Senior Managing Editor for AIhub.




            AIhub is supported by:


Related posts :



AI can be a powerful tool for scientists. But it can also fuel research misconduct

  31 Mar 2025
While AI is allowing scientists to make technological breakthroughs, there’s also a darker side to the use of AI in science: scientific misconduct is on the rise.
monthly digest

AIhub monthly digest: March 2025 – human-allied AI, differential privacy, and social media microtargeting

  28 Mar 2025
Welcome to our monthly digest, where you can catch up with AI research, events and news from the month past.

AI ring tracks spelled words in American Sign Language

  27 Mar 2025
In its current form, SpellRing could be used to enter text into computers or smartphones via fingerspelling.

How AI images are ‘flattening’ Indigenous cultures – creating a new form of tech colonialism

  26 Mar 2025
AI-generated stock images that claim to depict “Indigenous Australians”, don’t resemble Aboriginal and Torres Strait Islander peoples.

Interview with Lea Demelius: Researching differential privacy

  25 Mar 2025
We hear from doctoral consortium participant Lea Demelius who is investigating the trade-offs and synergies that arise between various requirements for trustworthy AI.

The Machine Ethics podcast: Careful technology with Rachel Coldicutt

This episode, Ben chats to Rachel Coldicutt about AI taxonomy, innovating for everyone not just the few, responsibilities of researchers, and more.

Interview with AAAI Fellow Roberto Navigli: multilingual natural language processing

  21 Mar 2025
Roberto tells us about his career path, some big research projects he’s led, and why it’s important to follow your passion.

Museums have tons of data, and AI could make it more accessible − but standardizing and organizing it across fields won’t be easy

  20 Mar 2025
How can AI models help organize large amounts of data from different collections, and what are the challenges?




AIhub is supported by:






©2024 - Association for the Understanding of Artificial Intelligence


 












©2021 - ROBOTS Association