1,722,263 research outputs found
On sketching approximations for symmetric Boolean CSPs
Get PDFA Boolean maximum constraint satisfaction problem, Max-CSP(), is specified
by a predicate . An -variable instance of
Max-CSP() consists of a list of constraints, each of which applies to
distinct literals drawn from the variables. For , Chou, Golovnev,
and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the
-space streaming approximability of every predicate. For ,
Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general
dichotomy theorem for -space sketching algorithms: For every ,
there exists such that for every ,
Max-CSP() is -approximable by an -space
linear sketching algorithm, but -approximation sketching
algorithms require space.
In this work, we give closed-form expressions for the sketching approximation
ratios of multiple families of symmetric Boolean functions. Letting , we show that for odd ,
AND, and for even , AND. We also resolve the ratio for the "at-least--'s"
function for all even ; the "exactly--'s" function for odd
; and fifteen other functions. We stress here that for
general , according to [CGSV21], closed-form expressions for
need not have existed a priori.
Separately, for all threshold functions, we give optimal "bias-based"
approximation algorithms generalizing [CGV20] while simplifying [CGSV21].
Finally, we investigate the -space streaming lower bounds in [CGSV21],
and show that they are incomplete for AND.Comment: 27 pages; same results but significant changes in presentatio
Scheduling of manufacturing systems based on extreme value theory and genetic algorithms
Get PDFThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering, 1995.Includes bibliographical references (p. 143-154).by Velusamy Subramaniam.Ph.D
Streaming approximation resistance of every ordering CSP
Get PDFAn ordering constraint satisfaction problem (OCSP) is defined by a family of predicates mapping permutations on to . An instance of Max-OCSP() on variables consists of a list of constraints, each consisting of a predicate from applied on distinct variables. The goal is to find an ordering of the variables that maximizes the number of constraints for which the induced ordering on the variables satisfies the predicate. OCSPs capture well-studied problems including `maximum acyclic subgraph\u27 (MAS) and maximum betweenness .
In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every , Max-OCSP() is approximation-resistant to -space streaming algorithms, i.e., algorithms using space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS our result shows that for every , MAS is not -approximable in space. The previous best inapproximability result, due to Guruswami and Tao (APPROX\u2719), only ruled out -approximations in space.
Our results build on a recent work of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC\u2722), who provide a tight, linear-space inapproximability theorem for a broad class of standard (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. We construct a family of appropriate standard CSPs from any given OCSP, apply their hardness result to this family of CSPs, and then convert back to our OCSP.21 pages, 1 figure. Abstract abridged. Appeared in APPROX\u2721 and Computational Complexit
Sketching Approximability of (Weak) Monarchy Predicates
Get PDFWe analyze the sketching approximability of constraint satisfaction problems
on Boolean domains, where the constraints are balanced linear threshold
functions applied to literals. In~particular, we explore the approximability of
monarchy-like functions where the value of the function is determined by a
weighted combination of the vote of the first variable (the president) and the
sum of the votes of all remaining variables. The pure version of this function
is when the president can only be overruled by when all remaining variables
agree. For every , we show that CSPs where the underlying predicate
is a pure monarchy function on variables have no non-trivial sketching
approximation algorithm in space. We also show infinitely many
weaker monarchy functions for which CSPs using such constraints are
non-trivially approximable by space sketching algorithms.
Moreover, we give the first example of sketching approximable asymmetric
Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan,
and Velusamy (FOCS 2021) that characterizes the sketching approximability of
all CSPs. Their framework can be applied naturally to get a computer-aided
analysis of the approximability of any specific constraint satisfaction
problem. The novelty of our work is in using their work to get an analysis that
applies to infinitely many problems simultaneously
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
Get PDFWe consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that
s(m,n,t) = ((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 .
In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that
s(m,n,t) = ((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}),
asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n.
In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m)
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Case comment: D. Velusamy v. D. Patchaiammal, (2010)10 SCC 469
Get PDFIn a country like India where laws are biased towards preservation of marriage, often at cost of women suffering, it is not surprising that the concept of ‘live-in relationship’ has been always considered unethical and immoral. However, moral policing cannot take away the fundamental rights sanctioned by the Constitution. The case of D. Velusamy v D. Patchaimal1 decided in 2010, generated a similar debate when the court through its ambiguous moral judgment, limited the scope of the expression ‘relationship in the nature of marriage’ under Section 2(f) of the Protection of Women from Domestic Violence Act2 and equated it with ‘commonlaw marriages’. While the judgement appears to be progressive by recognizing the legality of certain live-in relationships, it ended-up disadvantaging the women it seeks to protect. This comment attempts to critically analyse the Velusamy judgement and contends that by limiting the scope of the expression ‘relationship in the nature of marriage’, the court excluded women in a diverse range of cohabiting relationships, especially those who are in fraudulent marriages or are ‘second-wives’ from seeking legal remedies
Case Comment : D. VELUSAMY v. D. PATCHAIAMMAL, (2010)10 SCC 469
Get PDFIn a country like India where laws are biased towards the preservation of marriage, often at cost of women suffering, it is not surprising that the concept of ‘live-in relationship’ has been always considered unethical and immoral. However, moral policing cannot take away the fundamental rights sanctioned by the Constitution. The case of D. Velusamy v D. Patchaimal decided in 2010, generated a similar debate when the court through its ambiguous moral judgment, limited the scope of the expression ‘relationship in the nature of marriage’ under Section 2(f) of the Protection of Women from Domestic Violence Act and equated it with ‘common-law marriages. While the judgment appears to be progressive by recognizing the legality of certain live-in relationships, it ended up disadvantaging the women it seeks to protect. This comment attempts to critically analyse the Velusamy judgment and contends that by limiting the scope of the expression ‘relationship in the nature of marriage’, the court excluded women in a diverse range of cohabiting relationships, especially those who are in fraudulent marriages or are ‘second-wives’ from seeking legal remedies
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
