857 research outputs found
Central Asian Saks (Historical And Ethnographic Information)
No full textThe Article was devoted to the study historically ethnographically of antiquity about Central Asian Peoples of one of the ancestors (Saks). The author firstly provided information in this article on the reflection of the Saks in historical sources. In particular, the analysis of information and opinions about the Saks in the "Avesto", ancient Greek and Chinese sources One of the main aspects of the article is that it contains interesting information about the social life and customs of the Saks. The author has analyzed many sources and literature on the subject
Establishing Credibility: The Role of Foreign Advisors
Get PDFIn this paper I analyze the role of foreign advisors in stabilization programs. I discuss from an analytical perspective why foreigners may help a developing country's government put in place a successful stabilization program. This framework is used to analyze Chile's experience with anti-inflationary policies in the mid 1950s. In 1955-58 Chile implemented a stabilization package with the advice of the U.S. consulting firm of Klein-Saks. The Klein-Saks program took place in a period of acute political confrontation. After what was considered to be an initial success -- inflation declined from 85% in 1955 to 17% in 1957 -- the program failed to achieve durable price stability. I argue that the foreign advisors of the Klein-Saks Mission gave initial credibility to the stabilization program launched in 1955. But providing initial credibility was not enough to ensure success. Congress failed to act decisively on the fiscal front. Consequently the fiscal imbalances that had plagued Chile for a long time were reduced, but not eliminated. I present empirical results on the evolution of inflation, exchange rates and interest rates that support my historical analysis.
La Saks
Get PDFFilipinos are known for their strong sense of school spirit, and university merch is a way for students to show their pride in their institution. The popularity of sports events like the UAAP (University Athletic Association of the Philippines) has increased the demand for items showcasing affiliations, which created a market for merchandise beyond generic university logos. La Saks, established in September 2023, is a company that offers affordable ankle socks with a unique line of university-themed designs, which are marketed online on social media platforms and directly during the bazaar. As a general partnership type of organization, La Saks is led by five students: Andrea Tapis as Chief Executive Officer, Sherlyn Rodriguez as Chief Financial Officer, Ysabella Magpayo as Chief Operations Officer, Aicelle Pateres as Chief Marketing Officer, and Jeb Jandoc as Chief Procurement Officer. With Lasallian students being the target market, the main competitor of La Saks is Animo Nation, which is the official merchandise brand of De La Salle University. The shop offers a wide range of products. However, their high price range likely limits their reach to customers with tighter budgets. The initial investment of Php 11,455 successfully covered startup costs for inventory and bazaar participation. These initial sales, generating Php 21,500 in revenue, will be entirely reinvested for product diversification. Following the second selling cycle, the business will distribute 50% of the profits equally among the founders, while the remaining half will be reinvested for continued business growth
On Randomized Reductions to the Random Strings
Get PDFWe study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.
As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language L that has a randomized polynomial-time non-adaptive reduction (satisfying a natural honesty condition) to ω(log(n))-approximating the Kolmogorov complexity is in AM ∩ coAM. On the other hand, using results of Hirahara [Shuichi Hirahara, 2020], it follows that every language in NEXP has a randomized polynomial-time non-adaptive reduction (satisfying the same honesty condition as before) to O(log(n))-approximating the Kolmogorov complexity.
As our second main result, we give the first negative evidence against the NP-hardness of polynomial-time bounded Kolmogorov complexity with respect to randomized reductions. We show that for every polynomial t', there is a polynomial t such that if there is a randomized time t' non-adaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating K^t complexity, then either NE = coNE or has sub-exponential size non-deterministic circuits infinitely often
Local Enumeration and Majority Lower Bounds
Get PDFDepth-3 circuit lower bounds and k-SAT algorithms are intimately related; the state-of-the-art Σ^k_3-circuit lower bound (Or-And-Or circuits with bottom fan-in at most k) and the k-SAT algorithm of Paturi, Pudlák, Saks, and Zane (J. ACM'05) are based on the same combinatorial theorem regarding k-CNFs. In this paper we define a problem which reveals new interactions between the two, and suggests a concrete approach to significantly stronger circuit lower bounds and improved k-SAT algorithms. For a natural number k and a parameter t, we consider the Enum(k, t) problem defined as follows: given an n-variable k-CNF and an initial assignment α, output all satisfying assignments at Hamming distance t(n) of α, assuming that there are no satisfying assignments of Hamming distance less than t(n) of α. We observe that an upper bound b(n, k, t) on the complexity of Enum(k, t) simultaneously implies depth-3 circuit lower bounds and k-SAT algorithms:
- Depth-3 circuits: Any Σ^k_3 circuit computing the Majority function has size at least binom(n,n/2)/b(n, k, n/2).
- k-SAT: There exists an algorithm solving k-SAT in time O(∑_{t=1}^{n/2}b(n, k, t)).
A simple construction shows that b(n, k, n/2) ≥ 2^{(1 - O(log(k)/k))n}. Thus, matching upper bounds for b(n, k, n/2) would imply a Σ^k_3-circuit lower bound of 2^Ω(log(k)n/k) and a k-SAT upper bound of 2^{(1 - Ω(log(k)/k))n}. The former yields an unrestricted depth-3 lower bound of 2^ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis.
In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum(3, n/2). We show that the expected running time of our algorithm is 1.598ⁿ, substantially improving on the trivial bound of 3^{n/2} ≃ 1.732ⁿ. This already improves Σ^3_3 lower bounds for Majority function to 1.251ⁿ. The previous bound was 1.154ⁿ which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.'95).
By restricting ourselves to monotone CNFs, Enum(k, t) immediately becomes a hypergraph Turán problem. Therefore our techniques might be of independent interest in extremal combinatorics
Some properties of weak Banach-Saks operators
Get PDFWe establish necessary and sufficient conditions under which weak Banach-Saks operators are weakly compact (respectively, {\rm L}-weakly compact; respectively, {\rm M}-weakly compact). As consequences, we give some interesting characterizations of order continuous norm (respectively, reflexive Banach lattice)
Analogues of the Denjoy-Young-Saks theorem
No full textIn this paper, an analogue of the Denjoy-Young-Saks theorem concerning the almost everywhere classification of the Dini derivates of an arbitrary real function is established in both the case where the exceptional set is of first category and the case where it is
σ
\sigma
-porous. Examples are given to indicate the sharpness of these results.</p
The Weak Banach-Saks Property On L(P)(Mu,E)
No full textA Banach space E is said to have the Banach-Saks property (BS) if every bounded sequence {xn} in E has a subsequence with norm convergent Ces`aro means, i.e., 1 in E. If this occurs for every weakly convergent sequence in E, it is said that E has the weak Banach-Saks property (WBS).
It is known that uniformly convex spaces are BS,and E is BS iff E is WBS and reflexive. The spaces c0, `1, and L1 are WBS, whereas 1 and C[0, 1] are not. The BS and WBS properties do not pass from E to Lp(μ;E); in fact,
L2(c0) is not WBS [D. J. Aldous, Math. Proc. Camb. Philos. Soc. 85, 117-123 (1979;Zbl 0389.46027] and Bourgain constructed a Banach-Saks space E for which L2(E) is
not BS. Bourgain showed when the Banach-Saks property holds for Lp(μ,E) by using a property of L1 due to Koml´os; For every bounded sequence {fn} in L1(μ), there exists a
subsequence {f0 n } of {fn} and a f in L1(μ) such that 1
k Pk n=1 f0 n ! f almost everwhere for each subsequence {f0
n } of {f0 n }. When this holds in L1(μ,E), we say that L1(μ,E) has the Koml´os property. Bourgain showed that L1(μ,E) has the Koml´os property iff Lp(μ, e) is BS for some p 2 (1,1) iff Lp(μ,E) is BS for all p 2 (1,1). The author
uses ideas inspired by Bourgain’s work to similarly characterize WBS. She says that L1(μ,E) has the weak Koml´os property if every weakly null sequence {'n} in L1(μ,E)has the subsequence {'0 n} such that | 1 k Pk n=1 '0
n(·)| ! 0 almost everywhere for each subsequence {'0 n 0}of{'0 n}. She proves that L1(μ,E) is weak Banach-Saks iff Lp(μ,E)is WBS for some p 2 [1,1) iff Lp(μ,E) is WBS for all p 2 [1,1) iff L1(μ,E) is weak Koml´os. For example, if E is a B-convex Banach space, then L1(μ,E) is weak Koml´os and the above properties hold.Depto. de Análisis Matemático y Matemática AplicadaFac. de Ciencias MatemáticasTRUEpu
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Get PDFIn this paper we propose models of combinatorial algorithms for the Boolean
Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models.
First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976),
and we prove that the time required by any algorithm
for the BMM is at least Omega(n^3 / 2^{O( sqrt{ log n })}). Subsequently, we propose a more general model capable of simulating the
"Four Russian Algorithm". We prove a lower bound of Omega(n^{7/3} / 2^{O(sqrt{ log n })}) for the BMM under this model.
We use a special class of graphs, called (r,t)-graphs, originally discovered by Rusza and Szemeredi (1978),
along with randomization, to construct matrices that are hard instances for our combinatorial models
- …
