Publications related to Binary search algorithm

An Analysis of Super-Net Heuristics in Weight-Sharing NAS

Weight sharing promises to make neural architecture search (NAS) tractable even on commodity hardware. Existing methods in this space rely on a diverse set of heuristics to design and train the shared-weight backbone network, a.k.a. the super-net. Since he ...

IEEE COMPUTER SOC2022

Relatively robust decisions

Thomas Alois Weber

It is natural for humans to judge the outcome of a decision under uncertainty as a percentage of an ex-post optimal performance. We propose a robust decision-making framework based on a relative performance index. It is shown that if the decision maker's p ...

SPRINGER2022

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Gergely Odor

The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. I ...

2021

Landmark Regularization: Ranking Guided Super-Net Training in Neural Architecture Search

Mathieu Salzmann, Kaicheng Yu

Weight sharing has become a de facto standard in neural architecture search because it enables the search to be done on commodity hardware. However, recent works have empirically shown a ranking disorder between the performance of stand-alone architectures ...

IEEE COMPUTER SOC2021

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Giovanni De Micheli, Fereshte Mozafari Ghoraba, Heinz Riener, Giulia Meuli, Bruno Schmitt Antunes

We propose a flow for automated quantum compila- tion. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state pre ...

2021

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity

Volkan Cevher, Alp Yurtsever

This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an app ...

SIAM PUBLICATIONS2021

Scalable and Efficient Comparison-based Search without Features

Matthias Grossglauser, Lucas Maystre, Daniyar Chumbalov

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generate ...

2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Mika Tapani Göös

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

Square Attack: a query-efficient black-box adversarial attack via random search

Nicolas Henri Bernard Flammarion, Maksym Andriushchenko, Francesco Croce

We propose the Square Attack, a new score-based black-box

l_2

and

l_\infty

adversarial attack that does not rely on local gradient information and thus is not affected by gradient masking. The Square Attack is based on a randomized search scheme where ...

2020

Binary search algorithm

Graph Chatbot

Chat with Graph Search

An Analysis of Super-Net Heuristics in Weight-Sharing NAS

Relatively robust decisions

Sequential metric dimension for random graphs

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Landmark Regularization: Ranking Guided Super-Net Training in Neural Architecture Search

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity

Scalable and Efficient Comparison-based Search without Features

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Square Attack: a query-efficient black-box adversarial attack via random search

An Analysis of Super-Net Heuristics in Weight-Sharing NAS

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Square Attack: a query-efficient black-box adversarial attack via random search

Sequential metric dimension for random graphs

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity

Landmark Regularization: Ranking Guided Super-Net Training in Neural Architecture Search

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Relatively robust decisions

Scalable and Efficient Comparison-based Search without Features

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem