Publication

A size-sensitive inequality for cross-intersecting families

Publications associées (21)

SC-TPTP: An Extension of the TPTP Derivation Format for Sequent-Based Calculus

Motivated by the transfer of proofs between proof systems, and in particular from first order automated theorem provers (ATPs) to interactive theorem provers (ITPs), we specify an extension of the TPTP derivation text format to describe proofs in first-ord ...

2024

LISA – A Modern Proof System

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

We present LISA, a proof system and proof assistant for constructing proofs in schematic first-order logic and axiomatic set theory. The logical kernel of the system is a proof checker for first-order logic with equality and schematic predicate and fun ...

Dagstuhl, Germany, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik2023

A Gapless Post-quantum Hash Proof System in the Hamming Metric

Serge Vaudenay, Bénédikt Minh Dang Tran

A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap cause ...

2023

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Orcun Karaca, Baiwei Guo, Maryam Kamgarpour

We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the Eur ...

ELSEVIER2021

A dependence of the cost of fast controls for the heat equation on the support of initial datum

Hoài-Minh Nguyên

The controllability cost for the heat equation as the control time

T

goes to 0 is well-known of the order

e^{C/T}

for some positive constant

C

, depending on the controlled domain and for all initial datum. In this paper, we prove that the constant $C ...

2021

Forbidden induced subposets of given height

Istvan Tomon

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) su ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Some Proofs of Conditional and Joint Biases in RC4 Stream Cipher

Subhadeep Banik

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifi- cations and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 ...

2018

Theoretical Understanding of Some Conditional and Joint Biases in RC4 Stream Cipher

Subhadeep Banik

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in ...

IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG2018

Cloaking using complementary media in the quasistatic regime

Hoài-Minh Nguyên

Cloaking using complementary media was suggested by Lai et al. in [8]. The study of this problem faces two difficulties. Firstly, this problem is unstable since the equations describing the phenomenon have sign changing coefficients, hence the ellipticity ...

2016

Small subset sums

Gergely Ambrus

Let parallel to.parallel to be a norm in R-d whose unit ball is B. Assume that V subset of B is a finite set of cardinality n, with Sigma(v is an element of V) v = 0. We show that for every integer k with 0

Elsevier Science Inc2016

Separation with restricted families of sets

János Pach, Gábor Tardos, Márton Naszódi, Zsolt Langi

Given a finite n-element set X, a family of subsets F subset of 2(X) is said to separate X if any two elements of X are separated by at least one member of F. It is shown that if vertical bar F vertical bar > 2(n-1), then one can select vertical bar log n ...

Academic Press Inc Elsevier Science2016

Distinct Values Of Bilinear Forms On Algebraic Curves

Frank de Zeeuw, Adrian Claudiu Valculescu

Let B-M : C x C -> C be a bilinear form B-M(p, q) - p(T)Mq, with an invertible matrix M is an element of C-2x2. We prove that any finite set S contained in an irreducible algebraic curve C of degree d in C determines Omega(d)(vertical bar S vertical bar(4/ ...

Univ Calgary, Dept Math & Statistics2016

Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex

Jan Kyncl

We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant such that whenever are n-element subsets of , we can find a point and subsets for every , each of size at least , suc ...

Springer2015

Polynomiality of Hurwitz numbers, Bouchard-Marino conjecture, and a new proof of the ELSV formula

Nicolas Gerson Orantin

In this paper we give a new proof of the ELSV formula. First, we refine an argument of Okounkov and Pandharipande in order to prove (quasi-)polynomiality of Hurwitz numbers without using the ELSV formula (the only way to do that before used the ELSV formul ...

Academic Press Inc Elsevier Science2015

Superlensing using complementary media

Hoài-Minh Nguyên

This paper studies magnifying superlens using complementary media. Superlensing using complementary media was suggested by Veselago in [16] and innovated by Nicorovici et al. in [9] and Pendry in [10]. The study of this problem is difficult due to two fact ...

Gauthier-Villars/Editions Elsevier2015

Measuring the Dynamics of Contrast & Daylight Variability in Architecture: A Proof of Concept Methodology

Marilyne Andersen, Siobhan Francois Rockcastle

Unlike artificial light sources, which can be calibrated to meet a desired luminous effect regardless of latitude, climate, or time of day, daylight is a dynamic light source, which produces variable shadow patterns and fluctuating levels of brightness. Wh ...

Elsevier2014

Speculative Linearizability

Rachid Guerraoui, Viktor Kuncak, Giuliano Losa

Linearizability is a key design methodology for reasoning about implementations of concurrent abstract data types in both shared memory and message passing systems. It provides the illusion that operations execute sequentially and fault-free, despite the a ...

Assoc Computing Machinery2012

Epitome - A Social Game for Photo Album Summarization

Touradj Ebrahimi, Ivan Ivanov, Péter Vajda, Jong Seok Lee

In this paper, we propose an approach for photo album summarization through a novel social game "Epitome" for mobile phones. Our approach to album summarization consists of two games: "Select the Best!" and "Split it!". The goal of the first game is to all ...

2010

Stochastic Optimization of Sailing Trajectories in an America's Cup Race

Frédéric Dumas

The main objective of the thesis is the study and the determination of an optimal navigation strategy, for a sailboat in an America's Cup race, by methods of stochastic optimization. Such methods are appropriate because the sailing team expects the wind to ...

EPFL2010

Interactive Parallel Analysis on the ALICE Grid with the PROOF Framework

Marco Meoni

The ALICE experiment at CERN LHC is intensively using a PROOF cluster for fast analysis and reconstruction. The current system (CAF - CERN Analysis Facility) consists of 120 CPU cores and about 45 TB of local space. PROOF enables interactive parallel proce ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009