اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLinear Programming Relaxations for Goldreichs Generators over Non-Binary Alphabets
299
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Goldreich suggested candidates of one-way functions and pseudorandom generators included in $mathsf{NC}^0$. It is known that randomly generated Goldreichs generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$ output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreichs generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreichs generators. We assume that $u(n)in omega(1)cap o(n)$ input variables are known. In that case, we show that when $rge 3$, there is an exact threshold $mu_mathrm{c}(k,r):=binom{k}{r}^{-1}frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=mufrac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreichs generator if $mu>mu_mathrm{c}(k,r)$, and that the LP relaxation cannot determine $frac1{r-2} u(n)$ input variables of Goldreichs generator if $mu<mu_mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.
قيم البحث
اقرأ أيضاً
Chen, Kitaev, M{u}tze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character $diamond$, which is a placeholder for any l
etter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic $diamond$ structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size.
In this letter, we consider the Multi-Robot Efficient Search Path Planning (MESPP) problem, where a team of robots is deployed in a graph-represented environment to capture a moving target within a given deadline. We prove this problem to be NP-hard,
and present the first set of Mixed-Integer Linear Programming (MILP) models to tackle the MESPP problem. Our models are the first to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. While state-of-the-art algorithms for MESPP are based on simple path enumeration, the adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons. The models are designed for computing optimal solutions offline, but can be easily adapted for a distributed online approach. Our simulations show that it is possible to achieve 98% decrease in computational time relative to the previous state-of-the-art. We also show that the distributed approach performs nearly as well as the centralized, within 6% in the settings studied in this letter, with the advantage of requiring significant less time - an important consideration in practical search missions.
Ahlswede and Katona (1977) posed the following isodiametric problem in Hamming spaces: For every $n$ and $1le Mle2^{n}$, determine the minimum average Hamming distance of binary codes with length $n$ and size $M$. Fu, Wei, and Yeung (2001) used linea
r programming duality to derive a lower bound on the minimum average distance. However, their linear programming approach was not completely exploited. In this paper, we improve Fu-Wei-Yeungs bound by finding a better feasible solution to their dual program. For fixed $0<ale1/2$ and for $M=leftlceil a2^{n}rightrceil $, our feasible solution attains the asymptotically optimal value of Fu-Wei-Yeungs dual program as $ntoinfty$. Hence for $0<ale1/2$, all possible asymptotic bounds that can be derived by Fu-Wei-Yeungs linear program have been characterized. Furthermore, noting that the average distance of a code is closely related to weights of Fourier coefficients of a Boolean function, we also apply the linear programming technique to prove bounds on Fourier weights of a Boolean function of various degrees.
Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactl
y and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.
Recently, Wang et al. [IEEE INFOCOM 2011, 820-828], and Nie et al. [IEEE AINA 2014, 591-596] have proposed two schemes for secure outsourcing of large-scale linear programming (LP). They did not consider the standard form: minimize c^{T}x, subject to
Ax=b, x>0. Instead, they studied a peculiar form: minimize c^{T}x, subject to Ax = b, Bx>0, where B is a non-singular matrix. In this note, we stress that the proposed peculiar form is unsolvable and meaningless. The two schemes have confused the functional inequality constraints Bx>0 with the nonnegativity constraints x>0 in the linear programming model. But the condition x>0 is indispensable to the simplex method. Therefore, both two schemes failed.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
