Publications related to Communication complexity

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

A Wasserstein-based measure of conditional dependence

Negar Kiyavash, Seyed Jalal Etesami, Kun Zhang

Measuring conditional dependencies among the variables of a network is of great interest to many disciplines. This paper studies some shortcomings of the existing dependency measures in detecting direct causal influences or their lack of ability for group ...

2022

Computation Complexity Reduction Technique for Accurate Seizure Detection Implants

Alexandre Schmid, Keyvan Farhang Razi

An automatic seizure detection method from high-resolution intracranial-EEG (iEEG) signals is presented to minimize the computational complexity and realize real-time accurate seizure detection for biomedical implants. Complex signal processing on a large ...

IEEE2022

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

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

IEEE2022

Controlling the Complexity and Lipschitz Constant improves Polynomial Nets

Volkan Cevher, Grigorios Chrysos, Fabian Ricardo Latorre Gomez

While the class of Polynomial Nets demonstrates comparable performance to neural networks (NN), it currently has neither theoretical generalization characterization nor robustness guarantees. To this end, we derive new complexity bounds for the set of Coup ...

2022

On Succinct Non-interactive Arguments in Relativized Worlds

Alessandro Chiesa

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfort ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Communication complexity

Unambiguous DNFs and Alon-Saks-Seymour

A Wasserstein-based measure of conditional dependence

Computation Complexity Reduction Technique for Accurate Seizure Detection Implants

A Toolbox for Barriers on Interactive Oracle Proofs

A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Controlling the Complexity and Lipschitz Constant improves Polynomial Nets

On Succinct Non-interactive Arguments in Relativized Worlds

Lower Bounds for Unambiguous Automata via Communication Complexity

Relaxed Locally Correctable Codes With Nearly-Linear Block Length And Constant Query Complexity

Graph Chatbot

Chat with Graph Search

Unambiguous DNFs and Alon-Saks-Seymour

Computation Complexity Reduction Technique for Accurate Seizure Detection Implants

Relaxed Locally Correctable Codes With Nearly-Linear Block Length And Constant Query Complexity

A Toolbox for Barriers on Interactive Oracle Proofs

A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

On Succinct Non-interactive Arguments in Relativized Worlds

Lower Bounds for Unambiguous Automata via Communication Complexity

A Wasserstein-based measure of conditional dependence

Controlling the Complexity and Lipschitz Constant improves Polynomial Nets