326,989 research outputs found
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Get PDFGiven a set of n points in R^d, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the l_p-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d=omega(log n) was raised as an open question in recent works (Abboud-Rubinstein-Williams [FOCS'17], Williams [SODA'18], David-Karthik-Laekhanukit [SoCG'18]).
In this paper, we show that for every p in R_{>= 1} cup {0}, under the Strong Exponential Time Hypothesis (SETH), for every epsilon>0, the following holds:
- No algorithm running in time O(n^{2-epsilon}) can solve the Closest Pair problem in d=(log n)^{Omega_{epsilon}(1)} dimensions in the l_p-metric.
- There exists delta = delta(epsilon)>0 and c = c(epsilon)>= 1 such that no algorithm running in time O(n^{1.5-epsilon}) can approximate Closest Pair problem to a factor of (1+delta) in d >= c log n dimensions in the l_p-metric.
In particular, our first result is shown by establishing the computational equivalence of the bichromatic Closest Pair problem and the (monochromatic) Closest Pair problem (up to n^{epsilon} factor in the running time) for d=(log n)^{Omega_epsilon(1)} dimensions.
Additionally, under SETH, we rule out nearly-polynomial factor approximation algorithms running in subquadratic time for the (monochromatic) Maximum Inner Product problem where we are given a set of n points in n^{o(1)}-dimensional Euclidean space and are required to find a pair of distinct points in the set that maximize the inner product.
At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on n vertices with n^{2-epsilon} edges whose vertices can be realized as points in a (log n)^{Omega_epsilon(1)}-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Miccancio-Sudan [IEEE Trans. Inf. Theory'03]
Towards a General Direct Product Testing Theorem
Get PDFThe Direct Product encoding of a string a in {0,1}^n on an underlying domain V subseteq ([n] choose k), is a function DP_V(a) which gets as input a set S in V and outputs a restricted to S. In the Direct Product Testing Problem, we are given a function F:V -> {0,1}^k, and our goal is to test whether F is close to a direct product encoding, i.e., whether there exists some a in {0,1}^n such that on most sets S, we have F(S)=DP_V(a)(S). A natural test is as follows: select a pair (S,S')in V according to some underlying distribution over V x V, query F on this pair, and check for consistency on their intersection. Note that the above distribution may be viewed as a weighted graph over the vertex set V and is referred to as a test graph.
The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC '14) analyzed it when V equals the k-th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS '17) analyzed it for the case where V is the set of faces of a Ramanujan complex, where in this case V=O_k(n). In this paper, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem?
Towards this goal we introduce the notion of coordinate expansion of a test graph. Roughly speaking a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion then it admits a direct product testing theorem. Additionally, for every k and n we provide a direct product domain V subseteq (n choose k) of size n, called the Sliding Window domain for which we prove direct product testability
Ham Sandwich is Equivalent to Borsuk-Ulam
No full textThe Borsuk-Ulam theorem is a fundamental result in algebraic topology, with applications to various areas of Mathematics. A classical application of the Borsuk-Ulam theorem is the Ham Sandwich theorem: The volumes of any n compact sets in R^n can always be simultaneously bisected by an (n-1)-dimensional hyperplane.
In this paper, we demonstrate the equivalence between the Borsuk-Ulam theorem and the Ham Sandwich theorem. The main technical result we show towards establishing the equivalence is the following: For every odd polynomial restricted to the hypersphere f:S^n->R, there exists a compact set A in R^{n+1}, such that for every x in S^n we have f(x)=vol(A cap H^+) - vol(A cap H^-), where H is the oriented hyperplane containing the origin with x as the normal. A noteworthy aspect of the proof of the above result is the use of hyperspherical harmonics.
Finally, using the above result we prove that there exist constants n_0, epsilon_0>0 such that for every n>= n_0 and epsilon <= epsilon_0/sqrt{48n}, any query algorithm to find an epsilon-bisecting (n-1)-dimensional hyperplane of n compact set in [-n^4.51,n^4.51]^n, even with success probability 2^-Omega(n), requires 2^Omega(n) queries
On the Sensitivity Conjecture for Disjunctive Normal Forms
Get PDFThe sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function f, the maximum sensitivity s(f), is polynomially related to its block sensitivity bs(f), and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open.
In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function f admitting the Normalized Block property, bs(f) <= 4 * s(f)^2. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property.
Recently, Gopalan et al. [ITCS'16] showed that every Boolean function f is uniquely specified by its values on a Hamming ball of radius at most 2 * s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Get PDFThe k-Clique problem is a canonical hard problem in parameterized complexity.
In this paper, we study the parameterized complexity of approximating the
k-Clique problem where an integer k and a graph G on n vertices are given as
input, and the goal is to find a clique of size at least k/F(k) whenever the
graph G has a clique of size k. When such an algorithm runs in time T(k)poly(n)
(i.e., FPT-time) for some computable function T, it is said to be an
F(k)-FPT-approximation algorithm for the k-Clique problem.
Although, the non-existence of an F(k)-FPT-approximation algorithm for any
computable sublinear function F is known under gap-ETH [Chalermsook et al.,
FOCS 2017], it has remained a long standing open problem to prove the same
inapproximability result under the more standard and weaker assumption,
W[1]FPT.
In a recent breakthrough, Lin [STOC 2021] ruled out constant factor (i.e.,
F(k)=O(1)) FPT-approximation algorithms under W[1]FPT. In this paper, we
improve this inapproximability result (under the same assumption) to rule out
every factor FPT-approximation algorithm for any increasing
computable function H (for example ).
Our main technical contribution is introducing list decoding of Hadamard
codes over large prime fields into the proof framework of Lin
Elaunon bipartitus
No full text26. Elaunon bipartitus (Kirby, 1891) INDIA, Karnataka, Shivamogga, Savalanga, 14°5'5"N, 75°31'54"E, 634m, 24.xii.2021, Coll. Karthik, C. M., ex. Maize (8 males). INDIA, Karnataka, Chitradurga, Korechikkayyanaroppa, 14°2'24"N, 76°28'59"E, 716m, 10.vii.2022, Coll. Karthik, C. M., ex. Maize (5 males). INDIA, Andhra Pradesh, Chittur, S. V. Agriculture College, Tirupati, 13°37'30"N, 79°22'14"E, 193m, 23.iii.2021, Coll. Karthik, C. M., ex. Maize (4 males). INDIA, Telangana, Bhadradri Kothagudem, Agricultural College, Aswaraopet, 17°14'40"N, 81°6'2"E, 208m, 04.iv.2021, Coll. Sandeep., N. ex. Maize (3 males).Published as part of Karthik, C. M. & Kalleshwaraswamy, C. M., 2023, An annotated checklist of earwigs (Dermaptera) of South India with two new records from India, pp. 561-585 in Zootaxa 5330 (4) on page 570, DOI: 10.11646/zootaxa.5330.4.5, http://zenodo.org/record/825539
A Study on Mechanical Properties of E Glass Polypropylene Epoxy and S Glass Polypropylene Epoxy Composites
No full textThere are basic two phase of composite material, in which one is known as matrix material and another one is called reinforcing material. The reinforcing material is embedded over matrix material. The matrix material is continuous phase and reinforcing is discontinuous phase. The reinforcing phase is much harder than matrix phase. In composite material matrix phase removes the stresses between reinforcing phase and also protect from mechanical and environmental damage. The function of reinforcing material is to improve mechanical and thermal properties of composites. Composite are hybrid of two or more material such as reinforced polymer, metal or ceramics. The aim of the present work is to fabricate E glass epoxy composite and S glass epoxy composite with polypropylene as filler material. The fabricated laminates are then tested for mechanical properties with varying percentage of filler material. The results obtained for E glass epoxy composite and S glass epoxy composites are then compared. The composites with optimum results are recommended. Karthik A. S | Dr. S. V. Gorabal "A Study on Mechanical Properties of E-Glass Polypropylene Epoxy and S-Glass Polypropylene Epoxy Composites" Published in International Journal of Trend in Scientific Research and Development (ijtsrd), ISSN: 2456-6470, Volume-2 | Issue-5 , August 2018, URL: https://www.ijtsrd.com/papers/ijtsrd15903.pd
Hardness Amplification of Optimization Problems
Get PDFIn this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.
We say that an optimization problem Π is direct product feasible if it is possible to efficiently aggregate any k instances of Π and form one large instance of Π such that given an optimal feasible solution to the larger instance, we can efficiently find optimal feasible solutions to all the k smaller instances. Given a direct product feasible optimization problem Π, our hardness amplification theorem may be informally stated as follows:
If there is a distribution D over instances of Π of size n such that every randomized algorithm running in time t(n) fails to solve Π on 1/α(n) fraction of inputs sampled from D, then, assuming some relationships on α(n) and t(n), there is a distribution D' over instances of Π of size O(n⋅α(n)) such that every randomized algorithm running in time t(n)/poly(α(n)) fails to solve Π on 99/100 fraction of inputs sampled from D'.
As a consequence of the above theorem, we show hardness amplification of problems in various classes such as NP-hard problems like Max-Clique, Knapsack, and Max-SAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium
Communication Complexity of Correlated Equilibrium with Small Support
Get PDFWe define a two-player N x N game called the 2-cycle game, that has a unique pure Nash equilibrium which is also the only correlated equilibrium of the game. In this game, every 1/poly(N)-approximate correlated equilibrium is concentrated on the pure Nash equilibrium. We show that the randomized communication complexity of finding any 1/poly(N)-approximate correlated equilibrium of the game is Omega(N). For small approximation values, our lower bound answers an open question of Babichenko and Rubinstein (STOC 2017)
Diffusive author(s), cohesive author: Analysis of S/N (1994)
No full textThis study indicates the ways in which various aspects of the author(s) are brought forth in Dumb type’s performance art, the S/N production. Previous research has suggested a non-hierarchical organization of Dumb type and the absence of a “privileged author” in Dumb type’s collaborative work, S/N. However, the results that I have investigated from member’s interviews on the creative process of S/N along with my analysis of the recorded images of S/N, indicate a different aspect of the author(s). First, S/N was created through, so to speak, the collective ideas of the members of Dumb type. Further, S/N has at least nine quotations from previous performances, installations, and printed writings, besides the work-in-progress technique. Explicating one of the “author functions” as given by Michel Foucault, each text has plural subjects of the author. However, it has been revealed from members’ interviews that Teiji Furuhashi had a decision-making role in selecting the members’ ideas within the performance. Since then, S/N has had plural subjects of creation; however, Furuhashi is one of the subjects of creation along with the “privileged author.” S/N has plural authors (diffusive authors) yet at the same time, it has a “privileged author,” Teiji Furuhashi (cohesive author)
- …
