NP-completeness

Formal sciences
Theoretical computer science
Theory of computation
Computational complexity th...

About
Privacy
Disclaimer

Graph Chatbot

Related publications (31)

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

Alessandro Chiesa, Siqi Liu

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs. ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

NP Satisfiability for Arrays as Powers

Viktor Kuncak, Rodrigo Raya

We show that the satisfiability problem for the quantifier-free theory of product structures with the equicardinality relation is inNP. As an application, we extend the combinatory array logic fragmentto handle cardinality constraints. The resulting fragme ...

Springer, Cham2022

The Universal Gossip Fighter

Rachid Guerraoui, Anne-Marie Kermarrec, Anastasiia Kucherenko, Rafaël Benjamin Pinot

The notion of adversary is a staple of distributed computing. An adversary typically models “hostile” assumptions about the underlying distributed environment, e.g., a network that can drop messages, an operating system that can delay processes or an attac ...

IEEE2022

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Mario Bucev, Dragana Milovancevic

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023

Do Children Adapt Their Perspective to a Robot When They Fail to Complete a Task?

Pierre Dillenbourg, Elmira Yadollahi, Ana Paiva

Spatial understanding and communication are essential skills in human interaction. An adequate understanding of others' spatial perspectives can increase the quality of the interaction, both perceptually and cognitively. In this paper, we take the first st ...

Assoc Computing Machinery2022

Effect of Different Communication Affordances on the Emergence of Collaboration Strategies in an Online Multiplayer Game

Pierre Dillenbourg, Barbara Bruno, Hala Khodr, Aditi Kothiyal

In a group, the collective dynamics is governed by the inter- actions between individuals, which can manifest differently depending on the available means of communication. In this paper, we compare 3 conditions of communication affordances (global chat, l ...

Springer2022

Sound and Complete Verification of Polynomial Networks

Volkan Cevher, Grigorios Chrysos, Fanghui Liu, Mehmet Fatih Sahin, Elias Abad Rocamora

Polynomial Networks (PNs) have demonstrated promising performance on face and image recognition recently. However, robustness of PNs is unclear and thus obtaining certificates becomes imperative for enabling their adoption in real-world applications. Exist ...

2022

From C/C plus plus Code to High-Performance Dataflow Circuits

Paolo Ienne, Andrea Guerrieri, Lana Josipovic

High-level synthesis (HLS) tools typically generate statically scheduled datapaths. Static scheduling implies that the resulting circuits have a hard time exploiting parallelism in code with potential memory dependences, with control dependences, or where ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Automating cutting planes is NP-hard

Mika Tapani Göös

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It is -hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, ...

ACM2021

Bayesian Decision Making in Groups is Hard

Jan Hazla

We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior be ...

INFORMS2021

Imputation of missing information in worldwide patent data

Gaétan Jean A de Rassenfosse

We present a general method for imputing missing information in the Worldwide Patent Statistical Database (PATSTAT) and make the resulting datasets publicly available. The PATSTAT database is the de facto standard for academic research using patent data. C ...

2021

Page 2 of 2