Zobrazeno 1 - 10
of 102
pro vyhledávání: ''
Publikováno v:
IEEE Access, Vol 9, Pp 65482-65489 (2021)
A set of positive integers A is called a $g$ -Golomb ruler if the difference between two distinct elements of A is repeated up to $g$ times. This definition is a generalization of the Golomb ruler $(g = 1)$ . In this paper, we obtain new construction
Publikováno v:
LICS
36th IEEE Annual Symposium on Logic in Computer Science (LICS 2021)
36th IEEE Annual Symposium on Logic in Computer Science (LICS 2021), Jun 2021, Rome (on line), Italy
36th IEEE Annual Symposium on Logic in Computer Science (LICS 2021)
36th IEEE Annual Symposium on Logic in Computer Science (LICS 2021), Jun 2021, Rome (on line), Italy
LICS 2021 co-located with ITP 2021; International audience; The logics CS4 and IS4 are intuitionistic variants of the modal logic S4. Whether the finite model property holds for each of these logics has been a long-standing open problem. In this pape
Autor:
Ryan O'Donnell, Xinyu Wu
Publikováno v:
FOCS
Let p(Y1, …, Yd, Z1, …, Ze) be a self-adjoint noncommutative polynomial, with coefficients from $\mathrm{C}^{\mathrm{r}\times \mathrm{r}}$ , in the indeterminates Y1,…, Yd (considered to be self-adjoint), the indeterminates Z1, …, Ze, and the
Publikováno v:
FOCS
We say a probability distribution $\mu$ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if $\mu$ is spectrally independent, th
Autor:
Robert Robere, Toniann Pitassi, Marc Vinyals, Susanna F. de Rezende, Jakob Nordström, Or Meir
Publikováno v:
FOCS
University of Copenhagen
University of Copenhagen
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality
Autor:
Ashutosh Kumar, Vipul Goyal, Raghu Meka, David Zuckerman, Xin Li, Jesse Goodman, Eshan Chattopadhyay
Publikováno v:
FOCS
In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which $N$ parties, holding $n$ bits each, attempt to compute some joint function of their
Autor:
Yoshihiro Maruyama
Publikováno v:
FUZZ-IEEE
It is known that some fuzzy predicate logics, such as Łukasiewicz predicate logic, are not complete with respect to the standard real-valued semantics. In the present paper we focus upon a typed version of first-order MTL (Monoidal T-norm Logic), wh
Publikováno v:
FOCS
We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on $k$-tensors cannot yield non-trivial lower bounds on
Publikováno v:
FOCS
Longest common subsequence ($\mathsf{LCS}$) is a classic and central problem in combinatorial optimization. While $\mathsf{LCS}$ admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadrat
Autor:
C S Karthik, Vincent Cohen-Addad
Publikováno v:
FOCS
Proving hardness of approximation for min-sum objectives is an infamous challenge. For classic problems such as the Traveling Salesman problem, the Steiner tree problem, or the k-means and k-median problems, the best known inapproximability bounds fo