Publications related to Circuit complexity

Adventures in Monotone Complexity and TFNP

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone ...

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

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

ePrint2018

MATHICSE Technical Report : Analysis of stochastic gradient methods for PDE-constrained optimal control problems with uncertain parameters

Fabio Nobile, Sebastian Krumscheid, Matthieu Claude Martin

We consider the numerical approximation of a risk-averse optimal control problem for an elliptic partial differential equation (PDE) with random coefficients. Specifically, the control function is a deterministic, dis- tributed forcing term that minimizes ...

MATHICSE2018

Fast Approximate Spectral Clustering for Dynamic Networks

Pierre Vandergheynst, Lionel Jérémie Martin, Andreas Loukas

Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to get information from past cluster assignments to expedite computation. Our approach builds on a recen ...

2018

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Volkan Cevher, Ya-Ping Hsieh, Marwa El Halabi, Cong Bang Vu, Van Quang Nguyen

In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity ope ...

2017

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC

Colin Neil Jones, Ye Pu, Melanie Nicole Zeilinger

In this technical note, the fast alternating minimization algorithm (FAMA) is proposed to solve model predictive control (MPC) problems with polytopic and second-order cone constraints. Two splitting strategies with efficient implementations for MPC proble ...

2017

On Generalized Primal-Dual Interior-Point Methods with Non-uniform Complementarity Perturbations for Quadratic Programming

Colin Neil Jones, Altug Bitlislioglu

This technical note discusses convergence conditions of a generalized variant of primal-dual interior point methods. The generalization arises due to the permitted case of having a non-uniform complementarity perturbation vector, which is equivalent to hav ...

2017

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Michael Christoph Gastpar, Saeid Sahraei

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) ...

Institute of Electrical and Electronics Engineers2017

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.

Circuit complexity

Adventures in Monotone Complexity and TFNP

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

MATHICSE Technical Report : Analysis of stochastic gradient methods for PDE-constrained optimal control problems with uncertain parameters

Single-server Multi-user Private Information Retrieval with Side Information

Fast Approximate Spectral Clustering for Dynamic Networks

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC

On Generalized Primal-Dual Interior-Point Methods with Non-uniform Complementarity Perturbations for Quadratic Programming

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Graph Chatbot

Chat with Graph Search

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Fast Approximate Spectral Clustering for Dynamic Networks

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Single-server Multi-user Private Information Retrieval with Side Information

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear MPC

Adventures in Monotone Complexity and TFNP

MATHICSE Technical Report : Analysis of stochastic gradient methods for PDE-constrained optimal control problems with uncertain parameters