kth.sePublications

Please wait ... |

Jump to content
Change search PrimeFaces.cw("InputText","widget_formSmash_searchField",{id:"formSmash:searchField",widgetVar:"widget_formSmash_searchField"}); Search $(function(){PrimeFaces.cw("DefaultCommand","widget_formSmash_j_idt130",{id:"formSmash:j_idt130",widgetVar:"widget_formSmash_j_idt130",target:"formSmash:searchButton",scope:"formSmash:simpleSearch"});}); Search PrimeFaces.cw("CommandButton","widget_formSmash_searchButton",{id:"formSmash:searchButton",widgetVar:"widget_formSmash_searchButton"});
Only documents with full text in DiVA
PrimeFaces.cw("Fieldset","widget_formSmash_search",{id:"formSmash:search",widgetVar:"widget_formSmash_search",toggleable:true,collapsed:true,toggleSpeed:500,behaviors:{toggle:function(ext) {PrimeFaces.ab({s:"formSmash:search",e:"toggle",f:"formSmash",p:"formSmash:search"},ext);}}});
PrimeFaces.cw("InputText","widget_formSmash_upper_j_idt572",{id:"formSmash:upper:j_idt572",widgetVar:"widget_formSmash_upper_j_idt572"}); More stylesPrimeFaces.cw("InputText","widget_formSmash_upper_j_idt585",{id:"formSmash:upper:j_idt585",widgetVar:"widget_formSmash_upper_j_idt585"}); More languagesCreate PrimeFaces.cw("CommandButton","widget_formSmash_upper_j_idt594",{id:"formSmash:upper:j_idt594",widgetVar:"widget_formSmash_upper_j_idt594"}); Close PrimeFaces.cw("CommandButton","widget_formSmash_upper_j_idt595",{id:"formSmash:upper:j_idt595",widgetVar:"widget_formSmash_upper_j_idt595"});
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:upper:j_idt558",widgetVar:"citationDialog",width:"800",height:"600"});});
5 10 20 50 100 250 $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt609",{id:"formSmash:j_idt609",widgetVar:"widget_formSmash_j_idt609",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt609",e:"change",f:"formSmash",p:"formSmash:j_idt609"},ext);}}});});
Standard (Relevance) Author A-Ö Author Ö-A Title A-Ö Title Ö-A Publication type A-Ö Publication type Ö-A Issued (Oldest first) Issued (Newest first) Created (Oldest first) Created (Newest first) Last updated (Oldest first) Last updated (Newest first) Disputation date (earliest first) Disputation date (latest first) $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt623",{id:"formSmash:j_idt623",widgetVar:"widget_formSmash_j_idt623",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt623",e:"change",f:"formSmash",p:"formSmash:j_idt623"},ext);}}});});
Standard (Relevance) Author A-Ö Author Ö-A Title A-Ö Title Ö-A Publication type A-Ö Publication type Ö-A Issued (Oldest first) Issued (Newest first) Created (Oldest first) Created (Newest first) Last updated (Oldest first) Last updated (Newest first) Disputation date (earliest first) Disputation date (latest first) $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_j_idt627",{id:"formSmash:j_idt627",widgetVar:"widget_formSmash_j_idt627",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:j_idt627",e:"change",f:"formSmash",p:"formSmash:j_idt627"},ext);}}});});
all on this page PrimeFaces.cw("CommandButton","widget_formSmash_j_idt636",{id:"formSmash:j_idt636",widgetVar:"widget_formSmash_j_idt636"}); 250 onwards PrimeFaces.cw("CommandButton","widget_formSmash_j_idt637",{id:"formSmash:j_idt637",widgetVar:"widget_formSmash_j_idt637"});
Clear selection PrimeFaces.cw("CommandButton","widget_formSmash_j_idt639",{id:"formSmash:j_idt639",widgetVar:"widget_formSmash_j_idt639"});
$(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_j_idt642",{id:"formSmash:j_idt642",widgetVar:"widget_formSmash_j_idt642",target:"formSmash:selectHelpLink",showEffect:"blind",hideEffect:"fade",showCloseIcon:true});});
$(function(){PrimeFaces.cw("DataList","widget_formSmash_items_resultList",{id:"formSmash:items:resultList",widgetVar:"widget_formSmash_items_resultList"});});
PrimeFaces.cw("InputText","widget_formSmash_lower_j_idt1026",{id:"formSmash:lower:j_idt1026",widgetVar:"widget_formSmash_lower_j_idt1026"}); More stylesPrimeFaces.cw("InputText","widget_formSmash_lower_j_idt1036",{id:"formSmash:lower:j_idt1036",widgetVar:"widget_formSmash_lower_j_idt1036"}); More languagesCreate PrimeFaces.cw("CommandButton","widget_formSmash_lower_j_idt1045",{id:"formSmash:lower:j_idt1045",widgetVar:"widget_formSmash_lower_j_idt1045"}); Close PrimeFaces.cw("CommandButton","widget_formSmash_lower_j_idt1046",{id:"formSmash:lower:j_idt1046",widgetVar:"widget_formSmash_lower_j_idt1046"});
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:lower:j_idt1015",widgetVar:"citationDialog",width:"800",height:"600"});});

Refine search result

CiteExportLink to result list
http://kth.diva-portal.org/smash/resultList.jsf?query=&language=en&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A31572+OR+0000-0002-5379-345X%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt544_recordPermLink",{id:"formSmash:upper:j_idt544:recordPermLink",widgetVar:"widget_formSmash_upper_j_idt544_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt544_j_idt546",{id:"formSmash:upper:j_idt544:j_idt546",widgetVar:"widget_formSmash_upper_j_idt544_j_idt546",target:"formSmash:upper:j_idt544:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Cite

Citation styleapa ieee modern-language-association-8th-edition vancouver Other style $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt566",{id:"formSmash:upper:j_idt566",widgetVar:"widget_formSmash_upper_j_idt566",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt566",e:"change",f:"formSmash",p:"formSmash:upper:j_idt566",u:"formSmash:upper:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association-8th-edition
- vancouver
- Other style

Languagede-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Other locale $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt581",{id:"formSmash:upper:j_idt581",widgetVar:"widget_formSmash_upper_j_idt581",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:upper:j_idt581",e:"change",f:"formSmash",p:"formSmash:upper:j_idt581",u:"formSmash:upper:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Other locale

Output formathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_upper_j_idt591",{id:"formSmash:upper:j_idt591",widgetVar:"widget_formSmash_upper_j_idt591"});});

- html
- text
- asciidoc
- rtf

Rows per page

- 5
- 10
- 20
- 50
- 100
- 250

Sort

- Standard (Relevance)
- Author A-Ö
- Author Ö-A
- Title A-Ö
- Title Ö-A
- Publication type A-Ö
- Publication type Ö-A
- Issued (Oldest first)
- Issued (Newest first)
- Created (Oldest first)
- Created (Newest first)
- Last updated (Oldest first)
- Last updated (Newest first)
- Disputation date (earliest first)
- Disputation date (latest first)

- Standard (Relevance)
- Author A-Ö
- Author Ö-A
- Title A-Ö
- Title Ö-A
- Publication type A-Ö
- Publication type Ö-A
- Issued (Oldest first)
- Issued (Newest first)
- Created (Oldest first)
- Created (Newest first)
- Last updated (Oldest first)
- Last updated (Newest first)
- Disputation date (earliest first)
- Disputation date (latest first)

Select

The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.

1. Tight bounds for searching a sorted array of strings Andersson, A.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt672",{id:"formSmash:items:resultList:0:j_idt672",widgetVar:"widget_formSmash_items_resultList_0_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Hagerup, T.Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Petersson, O.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:0:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Tight bounds for searching a sorted array of strings2000In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 30, no 5, p. 1552-1578Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_0_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:0:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_0_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection [GRAPHICS] characters in the worst case.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:0:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 2. A new way of using semidefinite programming with applications to linear equations mod p Andersson, G.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt672",{id:"formSmash:items:resultList:1:j_idt672",widgetVar:"widget_formSmash_items_resultList_1_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Engebretsen, L.Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:1:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A new way of using semidefinite programming with applications to linear equations mod p2001In: Journal of Algorithms, ISSN 0196-6774, E-ISSN 1090-2678, Vol. 39, no 2, p. 162-204Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_1_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:1:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_1_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 - kappa (p))p, where kappa (p)> 0 for all p. Using standard techniques we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:1:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 3. Linear-consistency testing Aumann, Y.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt672",{id:"formSmash:items:resultList:2:j_idt672",widgetVar:"widget_formSmash_items_resultList_2_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Rabin, M. O.Sudan, M.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:2:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Linear-consistency testing2001In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 62, no 4, p. 589-607Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_2_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:2:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_2_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We extend the notion of linearity testing to the task of checking linear consistency of multiple functions. Informally, functions are linear if their graphs form straight lines on the plane. Two such functions are consistent if the lines have the same slope. We propose a variant of a test of M. Blum et al. (J. Comput. System Sci. 47 (1993), 549-595) to check the linear consistency of three functions f(1). f(2). f(3) mapping a finite Abelian group G to an Abelian group H: Pick x, y is an element of G uniformly and independently at random and check if f(1)(x) + f(2)(y) = f(3)(x + y). We analyze this test for two cases: (1) G and H are arbitrary Abelian groups and (2) G = F-2(n) and H = F-2. Questions bearing close relationship to linear-consistency testing seem to hav e been implicitly considered in recent work on the construction of PCPs and in particular in the work of J. Hastad [9] (in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. El Paso. Texas, 4-6 May 1997, pp. 1-10). It is abstracted explicitly for the first time here. As an application of our results we give yet another new and tight characterization of NP. namely For All epsilon > 0, NP = MIP1-epsilon 1/2 [O(log n), 3, 1]. That is, every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(log n) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1 - epsilon and rejects noninstances with probability at least;. Such a result is of some interest in the study of probabilistically checkable proofs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:2:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 4. On the usefulness of predicates Austrin, P.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt672",{id:"formSmash:items:resultList:3:j_idt672",widgetVar:"widget_formSmash_items_resultList_3_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:3:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the usefulness of predicates2012In: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), IEEE , 2012, p. 53-63Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_3_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:3:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_3_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Motivated by the pervasiveness of strong in approximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate P being \emph{useful} for a (real-valued) objective Q: given an almost satisfiable Max-P instance, there is an algorithm that beats a random assignment on the corresponding Max-Q instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate P is exactly the same as saying that P is useful for P itself. We say that P is useless if it is not useful for any Q. Under the Unique Games Conjecture, we can give a complete and simple characterization of useless Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pair wise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:3:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 5. Optimal inapproximability with universal factor graphs Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt669",{id:"formSmash:items:resultList:4:j_idt669",widgetVar:"widget_formSmash_items_resultList_4_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt672",{id:"formSmash:items:resultList:4:j_idt672",widgetVar:"widget_formSmash_items_resultList_4_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Brown-Cohen, JonahKTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.Håstad, JohanKTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:4:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Optimal inapproximability with universal factor graphs2021In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2021, p. 434-453Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_4_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:4:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_4_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: 1. Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). 2. Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). 3. Hardness of the “(2 + ε)-Sat” problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:4:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 6. (2 + ϵ)-SAT is NP-hard Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt669",{id:"formSmash:items:resultList:5:j_idt669",widgetVar:"widget_formSmash_items_resultList_5_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt672",{id:"formSmash:items:resultList:5:j_idt672",widgetVar:"widget_formSmash_items_resultList_5_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Guruswami, V.Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:5:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); (2 + ϵ)-SAT is NP-hard2017In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 5, p. 1554-1573Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_5_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:5:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_5_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = [w/2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat 2 P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed ϵ > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ϵ)-Sat" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ϵ. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:5:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 7. On the Usefulness of Predicates Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt669",{id:"formSmash:items:resultList:6:j_idt669",widgetVar:"widget_formSmash_items_resultList_6_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt672",{id:"formSmash:items:resultList:6:j_idt672",widgetVar:"widget_formSmash_items_resultList_6_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:6:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Usefulness of Predicates2012In: ACM Transactions on Computation Theory, ISSN 19423454, Vol. 5, no 1Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_6_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:6:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_6_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Motivated by the pervasiveness of strong inapproximability results forMax-CSPs, we introduce a relaxed notion of an approximate solution of aMax-CSP. In this relaxed version, loosely speaking, the algorithm is allowed toreplace the constraints of an instance by some other (possibly real-valued)constraints, and then only needs to satisfy as many of the new constraints aspossible.To be more precise, we introduce the following notion of a predicate $P$being \emph{useful} for a (real-valued) objective $Q$: given an almostsatisfiable Max-$P$ instance, there is an algorithm that beats a randomassignment on the corresponding Max-$Q$ instance applied to the same sets ofliterals. The standard notion of a nontrivial approximation algorithm for aMax-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for$P$ itself.We say that $P$ is useless if it is not useful for any $Q$. This turns out tobe equivalent to the following pseudo-randomness property: given an almostsatisfiable instance of Max-$P$ it is hard to find an assignment such that theinduced distribution on $k$-bit strings defined by the instance is notessentially uniform.Under the Unique Games Conjecture, we give a complete and simplecharacterization of useful Max-CSPs defined by a predicate: such a Max-CSP isuseless if and only if there is a pairwise independent distribution supportedon the satisfying assignments of the predicate. It is natural to also considerthe case when no negations are allowed in the CSP instance, and we derive asimilar complete characterization (under the UGC) there as well.Finally, we also include some results and examples shedding additional lighton the approximability of certain Max-CSPs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:6:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 8. Randomly supported independence and resistance Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt669",{id:"formSmash:items:resultList:7:j_idt669",widgetVar:"widget_formSmash_items_resultList_7_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt672",{id:"formSmash:items:resultList:7:j_idt672",widgetVar:"widget_formSmash_items_resultList_7_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Univ Toronto, Dept Comp Sci.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:7:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Randomly supported independence and resistance2011In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 1, p. 1-27Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_7_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:7:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_7_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that for any positive integers q and k there is a constant c(q,k) such that a uniformly random set of c(q,k)n(k) log n vectors in [q](n) with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument gives the stronger bound, c(q,k)n(k). Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting c(q,2)t(2) input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c'(q,k), such that a randomly selected set of cardinality c'(q,k)n(k) points is unlikely to support a balanced k-wise independent distribution and, for some c > 0, a random predicate accepting ct(2)/logt input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least (32/33).2(t) inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:7:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 9. Randomly Supported Independence and Resistance Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt669",{id:"formSmash:items:resultList:8:j_idt669",widgetVar:"widget_formSmash_items_resultList_8_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt672",{id:"formSmash:items:resultList:8:j_idt672",widgetVar:"widget_formSmash_items_resultList_8_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:8:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Randomly Supported Independence and Resistance2009In: STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, NEW YORK: ASSOC COMPUTING MACHINERY , 2009, p. 483-492Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_8_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:8:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_8_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that for any positive integer k, there is a constant C-k such that a randomly selected set of c(k)n(k) log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument, gives the strong-er bound ckn(k). Using a recent, result. by Austrin and Mossel this shows that a predicate on t, bits. Chosen at, random among predicates accepting c(2)t(2) input, vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These result's are close to tight,: we show that there are other constants, c(k)(1), such that a randomly selected set of points is unlikely to support a balanced k-wise. independent distribution and for some c > 0, a random predicate accepting ct(2)/log t input, vectors is is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (32/33) - 2(t) inputs is approximation resistant. The results extend front the Boolean domain to larger finite domains.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:8:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 10. (2 + epsilon)-Sat Is NP-hard Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt669",{id:"formSmash:items:resultList:9:j_idt669",widgetVar:"widget_formSmash_items_resultList_9_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt672",{id:"formSmash:items:resultList:9:j_idt672",widgetVar:"widget_formSmash_items_resultList_9_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Guruswami, V.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:9:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); (2 + epsilon)-Sat Is NP-hard2014In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, p. 1-10Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_9_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:9:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_9_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2]-1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT σ P as easiness of SAT when 1-in-2 literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when 1-in-3 literals are true, our resultshows, for any fixed &epsi; > 0, the hardness of finding a satisfyingassignment to instances of '(2 + &epsi;)-SAT' where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:9:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 11. On the power of many one-bit provers Austrin, Per PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt669",{id:"formSmash:items:resultList:10:j_idt669",widgetVar:"widget_formSmash_items_resultList_10_j_idt669",onLabel:"Austrin, Per ",offLabel:"Austrin, Per ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt672",{id:"formSmash:items:resultList:10:j_idt672",widgetVar:"widget_formSmash_items_resultList_10_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Pass, R.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:10:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the power of many one-bit provers2013In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, p. 215-220Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_10_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:10:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_10_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the class of languages, denoted by MIP[k, 1-∈, s], which have k-prover games where each prover just sends a single bit, with completeness 1-∈ and soundness error s. For the case that k=1 (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson (Computational Complexity'02) demonstrate that SZK exactly characterizes languages having 1-bit proof systems with "non-trivial" soundness (i.e., 1/2 < s ≤ 1-2∈). We demonstrate that for the case that k ≥ 2, 1-bit k-prover games exhibit a significantly richer structure: •(Folklore) When s ≤ 1/2 k - ∈, MIP[k, 1-∈, s] = BPP; • When 1/2k + ∈ ≤ s < 2/2k -∈, MIP[k, 1-∈, s] = SZK; • When s ≥ 2/2k + ∈, AM ⊆ MIP[k, 1-∈, s]; • For s ≤ 0.62 k/2k and sufficiently large k, MIP[k, 1-∈, s] ⊆ EXP; • For s ≥ 2k/2k, MIP[k, 1, 1-∈, s] = NEXP. As such, 1-bit k-prover games yield a natural "quantitative" approach to relating complexity classes such as BPP, SZK, AM, EXP, and NEXP. We leave open the question of whether a more fine-grained hierarchy (between AM and NEXP) can be established for the case when s ≥ 2/2k + ∈.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:10:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 12. Making the long code shorter Barak, B.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt672",{id:"formSmash:items:resultList:11:j_idt672",widgetVar:"widget_formSmash_items_resultList_11_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Gopalan, P.Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Meka, R.Raghavendra, P.Steurer, D.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:11:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Making the long code shorter2015In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 5, p. 1287-1324Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_11_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:11:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_11_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε > 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:11:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 13. Making the Long Code Shorter Barak, Boazet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_12_j_idt672",{id:"formSmash:items:resultList:12:j_idt672",widgetVar:"widget_formSmash_items_resultList_12_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Gopalan, ParikshitHåstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Meka, RaghuRaghavendra, PrasadSteurer, DavidPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:12:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Making the Long Code Shorter2012In: Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, IEEE Computer Society, 2012, p. 370-379Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_12_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:12:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_12_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1-ε, but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of Kpolylog(K), improving over the previously known gadget with blowup of 2Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:12:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 14. On DNF Approximators for Monotone Boolean Functions Blais, Ericet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt672",{id:"formSmash:items:resultList:13:j_idt672",widgetVar:"widget_formSmash_items_resultList_13_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Servedio, Rocco A.Tan, Li-YangPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:13:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On DNF Approximators for Monotone Boolean Functions2014In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, Springer Berlin/Heidelberg, 2014, Vol. 8572, p. 235-246Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_13_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:13:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_13_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the complexity of approximating monotone Boolean functions with disjunctive normal form (DNF) formulas, exploring two main directions. First, we construct DNF approximators for arbitrary monotone functions achieving one-sided error: we show that every monotone f can be e-approximated by a DNF g of size 2(n-Omega)(root n) satisfying g(x) <= f(x) for all x is an element of{0, 1}(n). This is the first non-trivial universal upper bound even for DNF approximators incurring two-sided error. Next, we study the power of negations in DNF approximators for monotone functions. We exhibit monotone functions for which non-monotone DNFs perform better than monotone ones, giving separations with respect to both DNF size and width. Our results, when taken together with a classical theorem of Quine [1], highlight an interesting contrast between approximation and exact computation in the DNF complexity of monotone functions, and they add to a line of work on the surprising role of negations in monotone complexity [2,3,4].

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:13:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 15. Bounded Independence vs. Moduli Boppana, R.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt672",{id:"formSmash:items:resultList:14:j_idt672",widgetVar:"widget_formSmash_items_resultList_14_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Lee, C. H.Viola, E.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:14:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Bounded Independence vs. Moduli2016In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2016Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_14_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:14:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_14_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0, 1}n that is supported on the set Sm := {x 2 {0, 1}n : Σi xi ≡ 0 mod m}, where m is any integer. We show that Ω(n/m2 logm) ≤ k ≤ 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over Sm. For any fixed odd m there is k ≥ (1-Ω(1))n such that any k-wise uniform distribution lands in Sm with probability exponentially close to |Sm|/2n; and this result is false for any even m.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:14:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 16. Bounded Independence versus Symmetric Tests Boppana, Ravi PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt669",{id:"formSmash:items:resultList:15:j_idt669",widgetVar:"widget_formSmash_items_resultList_15_j_idt669",onLabel:"Boppana, Ravi ",offLabel:"Boppana, Ravi ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt672",{id:"formSmash:items:resultList:15:j_idt672",widgetVar:"widget_formSmash_items_resultList_15_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); MIT, Dept Math, Cambridge, MA 02142 USA..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).Lee, Chin HoNortheastern Univ, Khoury Coll Comp Sci, 440 Huntington Ave,202 West Village H, Boston, MA 02115 USA..Viola, EmanueleNortheastern Univ, Khoury Coll Comp Sci, 440 Huntington Ave,202 West Village H, Boston, MA 02115 USA..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:15:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Bounded Independence versus Symmetric Tests2019In: ACM Transactions on Computation Theory, ISSN 1942-3454, E-ISSN 1942-3462, Vol. 11, no 4, article id 21Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_15_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:15:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_15_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); For a test T subset of {0, 1}(n), define k* (T) to be the maximum k such that there exists a k-wise uniform distribution over {0, 1}(n) whose support is a subset of T. For H-t = {x is an element of {0,1}(n) : vertical bar Sigma(i) x(i) - n/2 vertical bar <= t}, we prove k* (H-t) = Theta(t(2)/n + 1). For S-m,S-c = {x is an element of 1)(n) : Sigma(i )x(i) = c (mod m)}, we prove that k* (S-m,S-c) = Theta(n/m(2)). For some k = O(n/ m) we also show that any k-wise uniform distribution puts probability mass at most 1 /m + 1/100 over S-m,S-c. Finally, for any fixed odd m we show that there is an integer k = (1 - Omega(1))n such that any k-wise uniform distribution lands in T with probability exponentially close to vertical bar S-m,S-c vertical bar/2(n); and this result is false for any even m.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:15:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 17. An Improved Bound on the Fraction of Correctable Deletions Bukh, Boriset al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt672",{id:"formSmash:items:resultList:16:j_idt672",widgetVar:"widget_formSmash_items_resultList_16_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Guruswami, VenkatesanHåstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:16:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); An Improved Bound on the Fraction of Correctable Deletions2017In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 63, no 1, p. 93-103Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_16_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:16:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_16_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k >= 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1 - (2/(k + root k)). In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(root 2+1) = root 2-1 approximate to 0.414. Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1 - Theta (1/root k), and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 - Theta (1/k), since 1 - 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between (root 2 - 1) and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:16:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 18. Approximating linear threshold predicates Cheraghchi, M.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt672",{id:"formSmash:items:resultList:17:j_idt672",widgetVar:"widget_formSmash_items_resultList_17_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Isaksson, M.Svensson, O.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:17:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Approximating linear threshold predicates2012In: ACM Transactions on Computation Theory, ISSN 1942-3454, Vol. 4, no 1, p. 2-Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_17_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:17:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_17_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study constraint satisfaction problems on the domain {-1, 1}, where the given constraints are homogeneous linear threshold predicates, that is, predicates of the form sgn(w 1x 1 + Â· Â· Â· + w nx n) for some positive integer weights w 1, . . . , w n. Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this article is to identify and study the approximation curve of a class of threshold predicates that allow for nontrivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x 1 + Â· Â· Â· + x n), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:17:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 19. Approximating Linear Threshold Predicates Cheraghchi, Met al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt672",{id:"formSmash:items:resultList:18:j_idt672",widgetVar:"widget_formSmash_items_resultList_18_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.Isaksson, MSvensson, OlaKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:18:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Approximating Linear Threshold Predicates2010Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_18_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:18:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_18_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study constraint satisfaction problems on the domain {-1, 1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w(1)x(1) + ... + w(n)x(n)) for some positive integer weights w(1), ... ,w(n). Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. in fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x(1) + ... + x(n)), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:18:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 20. Randomness extraction and key derivation using the CBC, Cascade and HMAC Modes Dodis, Y.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt672",{id:"formSmash:items:resultList:19:j_idt672",widgetVar:"widget_formSmash_items_resultList_19_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Gennaro, R.Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Krawczyk, H.Rabin, T.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:19:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Randomness extraction and key derivation using the CBC, Cascade and HMAC Modes2004In: ADVANCES IN CRYPTOLOGY - CRYPTO 2004, PROCEEDINGS / [ed] Franklin, M, 2004, p. 494-510Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_19_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:19:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_19_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the suitability of common pseudorandomness modes associated with cryptographic hash functions and block ciphers (CBC-MAC, Cascade and HMAC) for the task of "randomness extraction", namely, the derivation of keying material from semi-secret and/or semi-random sources. Important applications for such extractors include the derivation of strong cryptographic keys from non-uniform sources of randomness (for example, to extract a seed for a pseudorandom generator from a weak source of physical or digital noise), and the derivation of pseudorandom keys from a Diffie-Hellman value. Extractors are closely related in their applications to pseudorandom functions and thus it is attractive to (re)use the common pseudorandom modes as randomness extractors. Yet, the crucial difference between pseudorandom generation and randomness extraction is that the former uses random secret keys while the latter uses random but known keys. We show that under a variety of assumptions on the underlying primitives (block ciphers and compression functions), ranging from ideal randomness assumptions to realistic universal-hashing properties, these modes induce good extractors. Hence, these schemes represent a more practical alternative to combinatorial extractors (that are seldom used in practice), and a better-analyzed alternative to the common practice of using SHA-1 or MD5 (as a single un-keyed function) for randomness extraction. In particular, our results serve to validate the method of key extraction and key derivation from Diffie-Hellman values used in the IKE (IPsec's Key Exchange) protocol.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:19:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 21. On lower bounds for selecting the median Dor, D.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt672",{id:"formSmash:items:resultList:20:j_idt672",widgetVar:"widget_formSmash_items_resultList_20_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Ulfberg, S.Zwick, U.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:20:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On lower bounds for selecting the median2001In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 14, no 3, p. 299-311Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_20_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:20:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_20_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We present a reformulation of the 2n + o(n) lower bound of Bent and John [Proceedings of the 17th Annual A CM Symposium on Theory of Computing, 1985, pp. 213-216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it. We use the new formulation to show that any pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing [n/2] disjoint pairs of elements must perform, in the worst case, at least 2.01n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn + o(n) comparisons for some c > 2.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:20:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 22. Quantum algorithms for computing short discrete logarithms and factoring RSA integers Ekerå, Martin PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt669",{id:"formSmash:items:resultList:21:j_idt669",widgetVar:"widget_formSmash_items_resultList_21_j_idt669",onLabel:"Ekerå, Martin ",offLabel:"Ekerå, Martin ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt672",{id:"formSmash:items:resultList:21:j_idt672",widgetVar:"widget_formSmash_items_resultList_21_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC). Swedish NCSA, Sweden.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:21:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Quantum algorithms for computing short discrete logarithms and factoring RSA integers2017In: 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017, Springer, 2017, Vol. 10346, p. 347-363Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_21_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:21:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_21_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekerå [2] so as to allow for various tradeoffs between the number of times that the algorithm need be executed on the one hand, and the complexity of the algorithm and the requirements it imposes on the quantum computer on the other hand. Furthermore, we describe applications of algorithms for computing short discrete logarithms. In particular, we show how other important problems such as those of factoring RSA integers and of finding the order of groups under side information may be recast as short discrete logarithm problems. This gives rise to an algorithm for factoring RSA integers that is less complex than Shor’s general factoring algorithm in the sense that it imposes smaller requirements on the quantum computer. In both our algorithm and Shor’s algorithm, the main hurdle is to compute a modular exponentiation in superposition. When factoring an n bit integer, the exponent is of length 2n bits in Shor’s algorithm, compared to slightly more than n/2 bits in our algorithm.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:21:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 23. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes Guruswami, V.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt672",{id:"formSmash:items:resultList:22:j_idt672",widgetVar:"widget_formSmash_items_resultList_22_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Harsha, P.Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Srinivasan, S.Varma, G.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:22:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Super-polylogarithmic hypergraph coloring hardness via low-degree long codes2014In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2014, p. 614-623Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_22_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:22:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_22_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques pro-posed by Dinur and Guruswami [FOCS 2013] to incorporatethis code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs: • Coloring a 2-colorable 8-uniform hypergraph with 2 2Ω(√log log n) colors. • Coloring a 4-colorable 4-uniform hypergraph with 22Ω(√ log log n) colors. • Coloring a 3-colorable 3-uniform hypergraph with (log n) Ω(1√ log log log n) colors. In each of these cases, the hardness results obtained are (at least) superpolynomially stronger (if not exponentially stronger as in the third case) than what was previously known for the respective cases. In fact, prior to this result, (log n)O(1) colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1)-colorable hypergraphs. The fundamental bottleneck in obtaining coloring in approximability results using the low-degree long code was a ultipartite structural restriction in the PCP construction of Dinur-Guruswami. We are able to get around this restriction by simulating the multipartite structure implicitly by querying just one partition (albeit requiring 8 queries), which yields our result for 2-colorable 8-uniform hypergraphs. The result for 4-colorable 4-uniform hypergraphs is obtained via a "query doubling" method exploiting additional properties of the 8-query test. For 3-colorable 3-uniform hyper-graphs, we exploit the ternary domain to design a test with an additive (as opposed to multiplicative) noise function, and analyze its efficacy in killing high weight Fourier coefficients via the pseudorandom properties of an associated quadratic form. The latter step involves extending the key algebraic ingredient of Dinur-Guruswami concerning testing binary Reed-Muller codes to the ternary alphabet.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:22:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 24. Explicit two-deletion codes with redundancy matching the existential bound Guruswami, V.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt672",{id:"formSmash:items:resultList:23:j_idt672",widgetVar:"widget_formSmash_items_resultList_23_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:23:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Explicit two-deletion codes with redundancy matching the existential bound2021In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2021, p. 21-32Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_23_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:23:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_23_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2n/n4). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Ω(2n/n3+o(1)) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:23:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 25. On the list-decodability of random linear codes Guruswami, V.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt672",{id:"formSmash:items:resultList:24:j_idt672",widgetVar:"widget_formSmash_items_resultList_24_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.Kopparty, S.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:24:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the list-decodability of random linear codes2010In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2010, p. 409-416Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_24_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:24:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_24_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We show that the list-decodability of random linear codes is as good as that of general random codes. Specifically, for every fixed finite field double-struck F

_{q}, p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in double-struck F_{q}^{n}of rate (1-H-q(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the "list decoding capacity" 1-H_{q}(p). The best previously known list-size bound was q^{O(1/ε)}(except in the q=2 case where a list-size bound of O(1/ε) was known). The main technical ingredient in our proof is a strong upper bound on the probability that ℓ random vectors chosen from a Hamming ball centered at the origin have too many (more than Θ(ℓ)) vectors from their linear span also belong to the ball.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:24:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 26. Hardness of approximate hypergraph coloring Guruswami, V.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt672",{id:"formSmash:items:resultList:25:j_idt672",widgetVar:"widget_formSmash_items_resultList_25_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Sudan, M.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:25:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Hardness of approximate hypergraph coloring2002In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 31, no 6, p. 1663-1686Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_25_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:25:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_25_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We introduce the notion of covering complexity of a veri er for probabilistically checkable proofs (PCPs). Such a veri er is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The veri er is also given a random string and decides whether to accept the proof or not, based on the given random string. We de ne the covering complexity of such a veri er, on a given input, to be the minimum number of proofs needed to satisfy the veri er on every random string; i.e., on every random string, at least one of the given proofs must be accepted by the veri er. The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems and, in particular, (hyper) graph coloring problems. We present a PCP veri er for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a superconstant covering complexity for statements not in the language. Moreover, the acceptance predicate of this veri er is a simple not-all-equal check on the four bits it reads. This enables us to prove that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:25:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 27. Combinatorial bounds for list decoding Guruswami, V.et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_26_j_idt672",{id:"formSmash:items:resultList:26:j_idt672",widgetVar:"widget_formSmash_items_resultList_26_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.Sudan, M.Zuckerman, D.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:26:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Combinatorial bounds for list decoding2002In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 48, no 5, p. 1021-1034Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_26_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:26:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_26_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Informally, an error-correcting code has nice list-decodability properties if every Hamming ball of large radius has a small number of codewords in it. Here, we report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H-1 (1-R-1/c) (.) n. This answers the main open question from the work of Elias. This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan in this vein. Specifically, for every epsilon > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Omega(epsilon(4)) that can be list-decoded in polynomial time from up to a fraction (1/2 - epsilon) of errors, using lists of size O(epsilon(-2)). On the negative side, we show that for every delta and c, there exists tau < delta, c(1) > 0, and an infinite family of linear codes {C-i}(i) such that if n(i) denotes the block length of C-i, then C-i has minimum distance at least delta (.) n(i) and contains more than c(1) (.) n(i)(c) codewords in some Hamming ball of radius tau (.) n(i). While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the radius for list-decodability by a polynomial-sized list away from the minimum distance of the code.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:26:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 28. SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES Guruswami, Venkatesanet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt672",{id:"formSmash:items:resultList:27:j_idt672",widgetVar:"widget_formSmash_items_resultList_27_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Harsha, PrahladhHåstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Srinivasan, SrikanthVarma, GirishPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:27:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES2017In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 1, p. 132-159Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_27_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:27:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_27_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the "short code" of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287-1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611-649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on n-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with 2(2 Omega(root loglg n)) colors; coloring a 4-colorable 4-uniform hypergraph with 2(2 Omega(root loglg n)) colors; and coloring a 3-colorable 3-uniform hypergraph with (log n)(Omega(1/log log log n)) colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, (log n)(O(1))Colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1) -colorable hypergraphs, and (log log n)(O(1)) for O(1) -colorable, 3-uniform hypergraphs.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:27:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 29. Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound Guruswami, Venkatesan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt669",{id:"formSmash:items:resultList:28:j_idt669",widgetVar:"widget_formSmash_items_resultList_28_j_idt669",onLabel:"Guruswami, Venkatesan ",offLabel:"Guruswami, Venkatesan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); et al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt672",{id:"formSmash:items:resultList:28:j_idt672",widgetVar:"widget_formSmash_items_resultList_28_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA..PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:28:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound2021In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 67, no 10, p. 6384-6394Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_28_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:28:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_28_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2(n)/n(4+o(1)). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Omega(2(n)/n(4)). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Omega(2(n)/n(3+o(1))) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:28:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 30. On the List-Decodability of Random Linear Codes Guruswami, Venkatesanet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt672",{id:"formSmash:items:resultList:29:j_idt672",widgetVar:"widget_formSmash_items_resultList_29_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Kopparty, SwastikPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:29:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the List-Decodability of Random Linear Codes2011In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, no 2, p. 718-725Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_29_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:29:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_29_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field, Gamma(q), p is an element of (0, 1 - 1/q) and epsilon > 0, it is proved that with high probability a random linear code C in F-q(n) of rate (1 - H-q(p) - epsilon) can be list decoded from a fraction p of errors with lists of size at most O(1/epsilon). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/epsilon) suffices to have rate within epsilon of the information-theoretically optimal rate of 1 - H-q(p). The best previously known list-size bound was q(O(1/epsilon)) (except in the q = 2 case where a list-size bound of O(1/epsilon) was known). The main technical ingredient in the proof is a strong upper bound on the probability that l random vectors chosen from a Hamming ball centered at the origin have too many (more than Omega(l)) vectors from their linear span also belong to the ball.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:29:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 31. BEATING THE RANDOM ORDERING IS HARD Guruswami, Venkatesanet al. PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt672",{id:"formSmash:items:resultList:30:j_idt672",widgetVar:"widget_formSmash_items_resultList_30_j_idt672",onLabel:"et al.",offLabel:"et al.",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Håstad, JohanKTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.Manokaran, RajsekarRaghavendra, PrasadCharikar, MosesPrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:30:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); BEATING THE RANDOM ORDERING IS HARD: EVERY ORDERING CSP IS APPROXIMATION RESISTANT2011In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 3, p. 878-914Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_30_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:30:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_30_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) where each constraint has constant arity is approximation resistant. In other words, we show that if. is the expected fraction of constraints satisfied by a random ordering, then obtaining rho' approximation for any rho' > rho is UG-hard. For the simplest OCSP, the MAXIMUM ACYCLIC SUBGRAPH (MAS) problem, this implies that obtaining a.-approximation for any constant rho > 1/2 is UG-hard. Specifically, for every constant epsilon > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsilon) of its edges, it is UG-hard to find one with more than (1/2 + epsilon) of its edges. Note that it is trivial to find an acyclic subgraph with 1/2 the edges by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied, and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset Pi subset of S-k of permutations on {1, 2, ... ,k}. An instance of such an OCSP is a set V and a collection of constraints, each of which is an ordered k-tuple of V. The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in.. A random ordering of V is expected to satisfy rho = vertical bar Pi vertical bar/k! fraction. We show that, for any fixed k, it is hard to obtain rho'-approximation for Pi-OCSP for any rho' > rho. The result is in fact stronger: we show that for every Lambda subset of Pi subset of S-k, and an arbitrarily small epsilon, it is hard to distinguish instances where a (1 - epsilon) fractionof the constraints can be ordered according to. from instances where at most a (rho + epsilon) fraction can be ordered as in Pi. A special case of our result is that the BETWEENNESS problem is hard to approximate beyond a factor 1/3. The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:30:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 32. A slight sharpening of LMN Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt669",{id:"formSmash:items:resultList:31:j_idt669",widgetVar:"widget_formSmash_items_resultList_31_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:31:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); A slight sharpening of LMN2001In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 63, no 3, p. 498-508Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_31_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:31:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_31_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); N. Linial et al. (1993. J. Assoc. Comput. Mach. 40, No. 3, 607-620) proved that a function computed by a small-depth circuit of limited size has most of its Fourier support on small sets. We improve their bounds. When the bottom fanin is bounded we use essentially their argument, but to reduce the general case to this case without a loss in the asymptotic bounds requires a new argument.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:31:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 33. An Average-case Depth Hierarchy Theorem for Higher Depths Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt669",{id:"formSmash:items:resultList:32:j_idt669",widgetVar:"widget_formSmash_items_resultList_32_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:32:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); An Average-case Depth Hierarchy Theorem for Higher Depths2016In: 2016 IEEE 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2016, Vol. 2016, p. 79-88Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_32_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:32:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_32_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We extend the recent hierarchy results of Ross-man, Servedio and Tan [1] to address circuits of almost logarithmic depth. Our proof uses the same basic approach as [1] but a number of small differences enables us to obtain a stronger result by a significantly shorter proof.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:32:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 34. Complexity theory, proofs and approximation Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt669",{id:"formSmash:items:resultList:33:j_idt669",widgetVar:"widget_formSmash_items_resultList_33_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:33:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Complexity theory, proofs and approximation2005In: European Congress of Mathematics / [ed] Laptev, A, 2005, p. 733-750Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_33_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:33:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_33_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We give a short introduction to some questions in complexity theory and proceed to describe some recent developments. In particular, we discuss probabilistically checkable proofs and their applications in establishing inapproximability results. In a traditional proof the proof-checker reads the entire proof and decides deterministically whether the proof is correct. In a probabilistically checkable proof the proof-checker randomly verifies only a very small portion of the proof but still cannot be fooled into accepting a false claim except with small probability.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:33:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 35. Every 2-CSP Allows Nontrivial Approximation Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt669",{id:"formSmash:items:resultList:34:j_idt669",widgetVar:"widget_formSmash_items_resultList_34_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:34:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Every 2-CSP Allows Nontrivial Approximation2005In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, p. 740-746Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_34_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:34:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_34_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does provably better than picking a random assignment. To be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d

^{2}possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d^{2}(1- c/d^{2}log d)) of optimal.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:34:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 36. EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt669",{id:"formSmash:items:resultList:35:j_idt669",widgetVar:"widget_formSmash_items_resultList_35_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:35:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION2008In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 17, no 4, p. 549-566Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_35_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:35:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_35_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does better than picking a random assignment. Specifically we consider the case when each variable can take values in [d] and that each constraint rejects t out of the d(2) possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, in expectation, within a factor 1 - t/d(2) + ct/d(4) log d of optimal, improving on the trivial bound of 1 - t/d(2).

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:35:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 37. Knuth Prize Lecture Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_36_j_idt669",{id:"formSmash:items:resultList:36:j_idt669",widgetVar:"widget_formSmash_items_resultList_36_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:36:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Knuth Prize Lecture: On the difficulty of approximating boolean max-CSPs2018In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2018, article id 8555141Conference paper (Refereed)38. On bounded occurrence constraint satisfaction Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_37_j_idt669",{id:"formSmash:items:resultList:37:j_idt669",widgetVar:"widget_formSmash_items_resultList_37_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, Superseded Departments (pre-2005), Mathematics.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:37:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On bounded occurrence constraint satisfaction2000In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 74, no 02-jan, p. 1-6Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_37_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:37:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_37_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); An approximation algorithm for a constraint satisfaction problem is said to be nontrivial if its performance ratio is strictly superior to the expected performance of the algorithm which simply chooses a random assignment. We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:37:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 39. On Nontrivial Approximation of CSPs Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt669",{id:"formSmash:items:resultList:38:j_idt669",widgetVar:"widget_formSmash_items_resultList_38_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:38:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On Nontrivial Approximation of CSPs2007Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_38_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:38:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_38_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); Constraint satisfaction problems, more simply called CSPs are central in computer science, the most famous probably being Satisfiability, SAT, the basic NP-complete problem. In this talk we survey some results about the optimization version of CSPs where we want to satisfy as many constraints as possible. One very simple approach to a CSP is to give random values to the variables. It turns out that for some CSPs, one example being Max-3Sat, unless P=NP, there is no polynomial time algorithm that can achieve a an approximation ratio that is superior to what is obtained by this trivial strategy. Some other CSPs, Max-Cut being a prime example, do allow very interesting non-trivial approximation algorithms which do give an approximation ratio that is substantially better than that obtained by a random assignment. These results hint at a general classification problem of determining which CSPs do admit a polynomial time approximation algorithm that beats the random assignment by a constant factor. Positive results giving such algorithms tend to be based on semi-definite programming while the PCP theorem is the central tool for proving negative result. We describe many of the known results in the area and also discuss some of the open problems.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:38:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 40. On small-depth Frege proofs for PHP Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt669",{id:"formSmash:items:resultList:39:j_idt669",widgetVar:"widget_formSmash_items_resultList_39_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:39:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On small-depth Frege proofs for PHP2023In: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, Institute of Electrical and Electronics Engineers (IEEE) , 2023, p. 37-49Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_39_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:39:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_39_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the n × n grid where n is odd. We are interested in the case where each formula in the proof is a depth d formula in the basis given by ∧, ∨, and ¬. We prove that in this situation the proof needs to be of size exponential in nΩ(1/d). If we restrict the size of each line in the proof to be of size M then the number of lines needed is exponential in n /(log M)O(d). The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:39:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 41. On Small-depth Frege Proofs for Tseitin for Grids Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt669",{id:"formSmash:items:resultList:40:j_idt669",widgetVar:"widget_formSmash_items_resultList_40_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:40:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On Small-depth Frege Proofs for Tseitin for Grids2021In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 68, no 1, article id 1Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_40_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:40:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_40_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that a small-depth Frege refutation of the Tseitin contradiction on the grid requires subexponential size. We conclude that polynomial size Frege refutations of the Tseitin contradiction must use formulas of almost logarithmic depth.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:40:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 42. On small-depth Frege proofs for Tseitin for grids Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_41_j_idt669",{id:"formSmash:items:resultList:41:j_idt669",widgetVar:"widget_formSmash_items_resultList_41_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:41:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On small-depth Frege proofs for Tseitin for grids2017In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, p. 97-108Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_41_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:41:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_41_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove a lower bound on the size of a small depth Frege refutation of the Tseitin contradiction on the grid. We conclude that polynomial size such refutations must use formulas of almost logarithmic depth.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:41:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 43. On the approximation resistance of a random predicate Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_42_j_idt669",{id:"formSmash:items:resultList:42:j_idt669",widgetVar:"widget_formSmash_items_resultList_42_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:42:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the approximation resistance of a random predicate2007In: Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques / [ed] Charikar, M; Reingold, O; Jansen, K; Rolim, JDP, BERLIN: SPRINGER-VERLAG BERLIN , 2007, Vol. 4627, p. 149-163Conference paper (Other academic)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_42_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:42:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_42_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A predicate is approximation resistant if no probabilistic polynomial time approximation algorithm can do significantly better then the naive algorithm that picks an assignment uniformly at random. Assuming that the Unique Games Conjecture is true we prove that most Boolean predicates are approximation resistant.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:42:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 44. On the Approximation Resistance of a Random Predicate Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt669",{id:"formSmash:items:resultList:43:j_idt669",widgetVar:"widget_formSmash_items_resultList_43_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:43:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the Approximation Resistance of a Random Predicate2009In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 18, no 3, p. 413-434Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_43_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:43:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_43_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); A predicate is called approximation resistant if it is NP-hard to approximate the corresponding constraint satisfaction problem significantly better than what is achieved by the naive algorithm that picks an assignment uniformly at random. In this paper we study predicates of Boolean inputs where the width of the predicate is allowed to grow. Samorodnitsky and Trevisan proved that, assuming the Unique Games Conjecture, there is a family of very sparse predicates that are approximation resistant. We prove that, under the same conjecture, any predicate implied by their predicate remains approximation resistant and that, with high probability, this condition applies to a randomly chosen predicate.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:43:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 45. On the correlation of parity and small-depth circuits Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_44_j_idt669",{id:"formSmash:items:resultList:44:j_idt669",widgetVar:"widget_formSmash_items_resultList_44_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:44:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the correlation of parity and small-depth circuits2014In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 43, no 5, p. 1699-1708Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_44_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:44:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_44_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that the correlation of a depth-d unbounded fanin circuit of size S with parity of n variables is at most 2(-Omega(n/(log S)d-1)).

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:44:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 46. On the efficient approximability of constraint satisfaction problems Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt669",{id:"formSmash:items:resultList:45:j_idt669",widgetVar:"widget_formSmash_items_resultList_45_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:45:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the efficient approximability of constraint satisfaction problems2007In: London Mathematical Society Lecture Notes, ISSN 0076-0552, Vol. 346, p. 201-222Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_45_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:45:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_45_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We discuss some results about the efficient approximability of constraint satisfaction problems. in particular we focus on the question on an efficient algorithm can perform significantly better than the algorithm that picks a solution uniformly at random.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:45:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 47. On the np-hardness of max-not-2 Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt669",{id:"formSmash:items:resultList:46:j_idt669",widgetVar:"widget_formSmash_items_resultList_46_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:46:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the np-hardness of max-not-22014In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 43, no 1, p. 179-193Article in journal (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_46_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:46:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_46_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that, for any epsilon > 0, given a satisfiable instance of Max-NTW (Not-2), it is NP-hard to find an assignment that satisfies a fraction 5/8 + epsilon of the constraints. This, up to the existence of epsilon, matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random, and thus the result is tight. Said equivalently, the result proves that Max-NTW is approximation resistant on satisfiable instances, and this makes complete our understanding of arity three maximum constraint satisfaction problems with regards to approximation resistance.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:46:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 48. On the NP-hardness of Max-Not-2 Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt669",{id:"formSmash:items:resultList:47:j_idt669",widgetVar:"widget_formSmash_items_resultList_47_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:47:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); On the NP-hardness of Max-Not-22012In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, p. 170-181Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_47_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:47:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_47_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We prove that, for any ε > 0, it is NP-hard to, given a satisfiable instance of Max-NTW (Not-2), find an assignment that satisfies a fraction 5/8 + ε of the constraints. This, up to the existence of ε, matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random and thus the result is tight. Said equivalently the result proves that Max-NTW is approximation resistant on satisfiable instances and this makes our understanding of arity three Max-CSPs with regards to approximation resistance complete.

PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:47:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 49. Satisfying degree-d equations of GF[2] Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt669",{id:"formSmash:items:resultList:48:j_idt669",widgetVar:"widget_formSmash_items_resultList_48_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:48:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Satisfying degree-d equations of GF[2]2011In: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization:: algorithms and techniques, 2011, p. 242-253Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_48_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:48:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_48_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over GF[2] of fixed constant degree

*d*> 1 and the aim is to satisfy the maximal number of equations. A random assignment approximates this problem within a factor 2^{-d}and we prove that for any ε > 0, it is NP-hard to obtain a ratio 2^{-d}+ ε. When considering instances that are perfectly satisfiable we give a probabilistic polynomial time algorithm that, with high probability, satisfies a fraction 2^{1-d}- 2^{1-2d}and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:48:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); 50. Satisfying Degree-<em>d</em> Equations of GF(2)<sup>n</sup> Håstad, Johan PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt669",{id:"formSmash:items:resultList:49:j_idt669",widgetVar:"widget_formSmash_items_resultList_49_j_idt669",onLabel:"Håstad, Johan ",offLabel:"Håstad, Johan ",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:orgPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); PrimeFaces.cw("Panel","testPanel",{id:"formSmash:items:resultList:49:etAlPanel",widgetVar:"testPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500}); Satisfying Degree-*d*Equations of GF(2)^{n}2011Conference paper (Refereed)Abstract [en] PrimeFaces.cw("SelectBooleanButton","widget_formSmash_items_resultList_49_j_idt714_0_j_idt715",{id:"formSmash:items:resultList:49:j_idt714:0:j_idt715",widgetVar:"widget_formSmash_items_resultList_49_j_idt714_0_j_idt715",onLabel:"Abstract [en]",offLabel:"Abstract [en]",onIcon:"ui-icon-triangle-1-s",offIcon:"ui-icon-triangle-1-e"}); We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over GF[2] of fixed constant degree d > 1 and the aim is to satisfy the maximal number of equations. A random assignment approximates this problem within a factor 2

^{−d}and we prove that for any ε > 0, it is NP-hard to obtain a ratio 2^{−d}+ε. When considering instances that are perfectly satisfiable we give a probabilistic polynomial time algorithm that, with high probability, satisfies a fraction 2^{1−d}− 2^{1−2d}and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.PrimeFaces.cw("Panel","tryPanel",{id:"formSmash:items:resultList:49:j_idt714:0:abstractPanel",widgetVar:"tryPanel",toggleable:true,toggleSpeed:500,collapsed:false,toggleOrientation:"vertical",closable:true,closeSpeed:500});

CiteExportLink to result list
http://kth.diva-portal.org/smash/resultList.jsf?query=&language=en&searchType=SIMPLE&noOfRows=50&sortOrder=author_sort_asc&sortOrder2=title_sort_asc&onlyFullText=false&sf=all&aq=%5B%5B%7B%22personId%22%3A%22authority-person%3A31572+OR+0000-0002-5379-345X%22%7D%5D%5D&aqe=%5B%5D&aq2=%5B%5B%5D%5D&af=%5B%5D $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_lower_j_idt1003_recordPermLink",{id:"formSmash:lower:j_idt1003:recordPermLink",widgetVar:"widget_formSmash_lower_j_idt1003_recordPermLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1003_j_idt1005",{id:"formSmash:lower:j_idt1003:j_idt1005",widgetVar:"widget_formSmash_lower_j_idt1003_j_idt1005",target:"formSmash:lower:j_idt1003:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Cite

Citation styleapa ieee modern-language-association-8th-edition vancouver Other style $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1021",{id:"formSmash:lower:j_idt1021",widgetVar:"widget_formSmash_lower_j_idt1021",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt1021",e:"change",f:"formSmash",p:"formSmash:lower:j_idt1021",u:"formSmash:lower:otherStyle"},ext);}}});});

- apa
- ieee
- modern-language-association-8th-edition
- vancouver
- Other style

Languagede-DE en-GB en-US fi-FI nn-NO nn-NB sv-SE Other locale $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1032",{id:"formSmash:lower:j_idt1032",widgetVar:"widget_formSmash_lower_j_idt1032",behaviors:{change:function(ext) {PrimeFaces.ab({s:"formSmash:lower:j_idt1032",e:"change",f:"formSmash",p:"formSmash:lower:j_idt1032",u:"formSmash:lower:otherLanguage"},ext);}}});});

- de-DE
- en-GB
- en-US
- fi-FI
- nn-NO
- nn-NB
- sv-SE
- Other locale

Output formathtml text asciidoc rtf $(function(){PrimeFaces.cw("SelectOneMenu","widget_formSmash_lower_j_idt1042",{id:"formSmash:lower:j_idt1042",widgetVar:"widget_formSmash_lower_j_idt1042"});});

- html
- text
- asciidoc
- rtf