Publications associées à Proofs, Circuits, and Communication

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Colin Neil Jones, Yuning Jiang, Yingzhao Lian, Xinliang Dai

This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...

New York2023

Minimum Cost Intervention Design for Causal Effect Identification

Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

PMLR2022

Communication Complexity of Collision

Mika Tapani Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...

Leibniz-Zentrum für Informatik2022

On Semi-Algebraic Proofs and Algorithms

Mika Tapani Göös

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

A Toolbox for Barriers on Interactive Oracle Proofs

Alessandro Chiesa

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Further Collapses in TFNP

Mika Tapani Göös, Gilbert Théodore Maystre, Alexandros Paul Hollender, Siddhartha Jain, Ran Tao

We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

Giovanni De Micheli, Heinz Riener, Siang-Yun Lee

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...

IEEE2021

String Matching: Communication, Circuits, and Learning

Mika Tapani Göös

String matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings. - Communication complexity. For small k, we provide near-optimal upper and lower bounds on th ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2019

Proofs, Circuits, and Communication

Graph Chatbot

Chattez avec Graph Search

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Minimum Cost Intervention Design for Causal Effect Identification

Communication Complexity of Collision

On Semi-Algebraic Proofs and Algorithms

A Toolbox for Barriers on Interactive Oracle Proofs

Further Collapses in TFNP

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

On Calculating the Minimum Rate for the Cooperative Data Exchange Problem Over Fully Connected Networks

String Matching: Communication, Circuits, and Learning

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Minimum Cost Intervention Design for Causal Effect Identification

Communication Complexity of Collision

On Semi-Algebraic Proofs and Algorithms

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

On Calculating the Minimum Rate for the Cooperative Data Exchange Problem Over Fully Connected Networks

String Matching: Communication, Circuits, and Learning

A Toolbox for Barriers on Interactive Oracle Proofs

Further Collapses in TFNP

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches