On Semi-Algebraic Proofs and Algorithms

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.

How to measure students' Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types ( ...

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

According to physicalism, everything is physical or metaphysically connected to the physical. If physicalism were true, it seems that we should - in principle - be able to reduce the descriptions and explanations of special sciences to physical ones, for e ...

We present a robust model predictive control (MPC) framework for linear systems facing bounded parametric uncertainty and bounded disturbances. Our approach deviates from standard MPC formulations by integrating multi-step predictors, which provide reduced ...

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Self-attention mechanisms and non-local blocks have become crucial building blocks for state-of-the-art neural architectures thanks to their unparalleled ability in capturing long-range dependencies in the input. However their cost is quadratic with the nu ...

The SALUTE project aims at evaluating performance of electroacoustic metasurface, employing a surface array of controlled electroacoustic actuators, for smart acoustic lining under grazing turbulent flow to be used in UHBR Technologies Engines. Theoretical ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Linear-Quadratic-Gaussian (LQG) control is a fundamental control paradigm that is studied in various fields such as engineering, computer science, economics, and neuroscience. It involves controlling a system with linear dynamics and imperfect observations ...

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assu ...

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 ...

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 ...

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...

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 ...

On Semi-Algebraic Proofs and Algorithms

Chat with Graph Search

A Comparative Analysis of Tools & Task Types for Measuring Computational Problem-Solving

Efficient Continual Finite-Sum Minimization

Inhalation of Microplastics—A Toxicological Complexity

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Graph generative deep learning models with an application to circuit topologies

Why computational complexity may set impenetrable barriers for epistemic reductionism

Homothetic Tube Model Predictive Control With Multi-Step Predictors

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Linear Complexity Self-Attention With 3rd Order Polynomials

Smart acoustic lining for UHBR technologies engine: from the design of an electroacoustic metasurface to experimental characterization under flow

Approximation Algorithms for Allocation and Network Design

Distributionally Robust Linear Quadratic Control

Proofs, Circuits, and Communication

Discrete Optimal Transport with Independent Marginals is #P-Hard

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Computation Complexity Reduction Technique for Accurate Seizure Detection Implants

A Toolbox for Barriers on Interactive Oracle Proofs

Efficient Preparation of Cyclic Quantum States

Symmetry in design and decoding of polar-like codes

A Wasserstein-based measure of conditional dependence