kth.sePublications
Change search
Refine search result
1234567 1 - 50 of 518
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • 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. Abrahamsson, H
    et al.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Marsh, Ian
    TCP over high speed variable capacity links: A simulation study for bandwidth allocation2002Conference paper (Refereed)
    Abstract [en]

     New optical network technologies provide opportunities for fast, controllable bandwidth management. These technologies can now explicitly provide resources to data paths, creating demand driven bandwidth reservation across networks where an applications bandwidth needs can be meet almost exactly. Dynamic synchronous Transfer Mode (DTM) is a gigabit network technology that provides channels with dynamically adjustable capacity. TCP is a reliable end-to-end transport protocol that adapts its rate to the available capacity. Both TCP and the DTM bandwidth can react to changes in the network load, creating a complex system with inter-dependent feedback mechanisms. The contribution of this work is an assessment of a bandwidth allocation scheme for TCP flows on variable capacity technologies. We have created a simulation environment using ns-2 and our results indicate that the allocation of bandwidth maximises TCP throughput for most flows, thus saving valuable capacity when compared to a scheme such as link over-provisioning. We highlight one situation where the allocation scheme might have some deficiencies against the static reservation of resources, and describe its causes. This type of situation warrants further investigation to understand how the algorithm can be modified to achieve performance similar to that of the fixed bandwidth case.

  • 2. Adrian, K.
    et al.
    Chocron, P.
    Confalonieri, R.
    Ferrer, X.
    Giráldez-Cru, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Link prediction in evolutionary graphs the case study of the CCIA network2016In: 19th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2016, IOS Press, 2016, p. 187-196Conference paper (Refereed)
    Abstract [en]

    Studying the prediction of new links in evolutionary networks is a captivating question that has received the interest of different disciplines. Link prediction allows to extract missing information and evaluate network dynamics. Some algorithms that tackle this problem with good performances are based on the sociability index, a measure of node interactions over time. In this paper, we present a case study of this predictor in the evolutionary graph that represents the CCIA co-authorship network from 2005 to 2015. Moreover, we present a generalized version of this sociability index, that takes into account the time in which such interactions occur. We show that this new index outperforms existing predictors. Finally, we use it in order to predict new co-authorships for CCIA 2016.

  • 3.
    Aktug, Irem
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Algorithmic Verification Techniques for Mobile Code2008Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    Modern computing platforms strive to support mobile code without putting system security at stake. These platforms can be viewed as open systems, as the mobile code adds new components to the running system. Establishing that such platforms function correctly can  be divided into two steps. First, it is shown that the system functions correctly regardless of the mobile components that join it, provided that they satisfy certain assumptions. These assumptions can, for instance, restrict the behavior of the component to ensure that the security policy of the platform is not violated. Second, the mobile component is checked to satisfy its assumptions, before it is allowed to join the system. This thesis presents algorithmic verification techniques to support this methodology. In the first two parts, we present techniques for the verification of open systems relative to the given component assumptions. In the third part, a technique for the  quick certification of mobile code is presented for the case where a particular type of program rewriting is used as a means of enforcing the component assumptions.In the first part of this study, we present a framework for the verification of open systems based on explicit state space representation. We propose Extended Modal Transition Systems (EMTS) as a suitable structure for representing the state space of open systems when assumptions on components are written in the modal μ-calculus. EMTSs are based on the Modal Transition Systems (MTS) of Larsen and provide a formalism for graphical specification and facilitate a thorough understanding of the system by visualization. In interactive verification, this state space representation enables proof reuse and aids the user guiding the verification process. We present a construction of state space representations from process algebraic open system descriptions based on a maximal model construction for the modal μ-calculus. The construction is sound and complete for systems with a single unknown component and sound for those without dynamic process reation. We also suggest a tableau-based proof system for establishing temporal properties of open systems represented as EMTS. The proof system is sound in general and complete for prime formulae.The problem of open system correctness  also arises in compositional verification, where the problem of showing a global property of a system is reduced to showing local properties of components. In the second part, we extend an existing  compositional verification framework for Java bytecode programs. The framework employs control flow graphs with procedures to model component implementations and open systems for the purpose of checking control-flow properties. We generalize these models to capture exceptional and multi-threaded behavior. The resulting control flow graphs are specifically tailored to support the compositional verification principle; however, they are sufficiently intuitive and standard to be useful on their own. We describe how the models can be extracted from program code and give preliminary experimental results for our implementation of the extraction of control flow graphs with exceptions. We also discuss further tool support and practical applications of the method.In the third part of the thesis, we develop a technique for the certification of safe mobile code, by adapting the proof-carrying code scheme of Necula to the case of security policies expressed as security automata. In particular, we describe how proofs of policy compliance can  be automatically generated for  programs that include a monitor for the desired policy. A monitor is an entity that observes the execution of a program and terminates the program if a violation to the property is about to occur. One way to implement such a monitor is by rewriting the program to make it self-monitoring. Given a property, we characterize self-monitoring of Java bytecode programs for this property by an annotation scheme with annotations in the style of Floyd-Hoare logics. The annotations generated by this scheme can be extended in a straightforward way to form a correctness proof in the sense of axiomatic semantics of programs. The proof generated in this manner essentially establishes that the program satisfies the property because it contains a monitor for it. The annotations that comprise the proofs are simple and efficiently checkable, thus facilitate certification of mobile code on devices with restricted computing power such as mobile phones.

    Download full text (pdf)
    FULLTEXT01
  • 4.
    Aktug, Irem
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Dam, Mads
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Provably Correct Runtime Monitoring2009In: Journal of Logic and Algebraic Programming, ISSN 1567-8326, E-ISSN 1873-5940, Vol. 78, no 5, p. 304-339Article in journal (Refereed)
    Abstract [en]

    Runtime monitoring is an established technique to enforce a wide range of program safety and security properties. We present a formalization of monitoring and monitor inlining, for the Java Virtual Machine. Monitors are security automata given in a special-purpose monitor specification language, ConSpec. The automata operate on finite or infinite strings of calls to a fixed API, allowing local dependencies on parameter values and heap content. We use a two-level class file annotation scheme to characterize two key properties: (i) that the program is correct with respect to the monitor as a constraint on allowed program behavior, and (ii) that the program has a copy of the given monitor embedded into it. As the main application of these results we sketch a simple inlining algorithm and show how the two-level annotations can be completed to produce a fully annotated program which is valid in the standard sense of Floyd/Hoare logic. This establishes the mediation property that inlined programs are guaranteed to adhere to the intended policy. Furthermore, validity can be checked efficiently using a weakest precondition based annotation checker, thus preparing the ground for on-device checking of policy adherence in a proof-carrying code setting.

  • 5.
    Aktug, Irem
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Dam, Mads
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Provably correct runtime monitoring (extended abstract)2008In: Fm 2008: Formal Methods, Proceedings / [ed] Cuellar, J; Maibaum, T; Sere, K, 2008, Vol. 5014, p. 262-277Conference paper (Refereed)
    Abstract [en]

    Runtime monitoring is an established technique for enforcing a wide range of program safety and security properties. We present a formalization of monitoring and monitor inlining, for the Java Virtual Machine. Monitors are security automata given in a special-purpose monitor specification language, ConSpec. The automata operate on finite or infinite strings of calls to a fixed API, allowing local dependencies on parameter values and heap content. We use a two-level class file annotation scheme to characterize two key properties: (i) that the program is correct with respect to the monitor as a constraint on allowed program behavior, and (ii) that the program has an instance of the given monitor embedded into it, which yields state changes at prescribed points according to the monitor's transition function. As our main application of these results we describe a concrete inliner, and use the annotation scheme to characterize its correctness. For this inliner, correctness of the level II annotations can be decided efficiently by a weakest precondition annotation checker, thus allowing on-device checking of inlining correctness in a proof-carrying code setting.

  • 6.
    Aktug, Irem
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Towards State Space Exploration Based Verification of Open Systems2005In: 4th International Workshop on Automated Verification of Infinite-State Systems (AVIS’05), April 2005, Edinburgh, Scotland, 2005Conference paper (Refereed)
  • 7.
    Aktug, Irem
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Naliuka, Katsiaryna
    University of Trento, Italy.
    ConSpec: A Formal Language for Policy Specification2008In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 74, no 1-2, p. 2-12Article in journal (Refereed)
    Abstract [en]

    The paper presents ConSpec, an automata-based policy specification language. The language trades off clean semantics to language expressiveness: a formal semantics for the language is provided as security automata. ConSpec specifications can be used at different stages of the application lifecycle, rendering possible the formalization of various Policy enforcement techniques.

  • 8.
    Aktug, Irem
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Naliuka, Katsiaryna
    University of Trento, Italy.
    ConSpec: A Formal Language for Policy Speci-fication2007In: Proceedings of The First International Workshop on Run Time Enforcement for Mobile and Distributed Systems (REM’07), 2007, p. 45-58Conference paper (Other academic)
    Abstract [en]

    The paper presents ConSpec, an automata based policy specification language. The language trades off clean semantics to language expressiveness; a formal semantics for the language is provided as security automata. ConSpec specifications can be used at different stages of the application lifecycle, rendering possible the formalization of various policy enforcement techniques.

  • 9. Allan, James
    et al.
    Aslam, Jay
    Azzopardi, Leif
    Belkin, Nick
    Borlund, Pia
    Bruza, Peter
    Callan, Jamie
    Carman, Mark
    Clarke, Charles L.A.
    Craswell, Nick
    Croft, W. Bruce
    Culpepper, J. Shane
    Diaz, Fernando
    Dumais, Susan
    Ferro, Nicola
    Geva, Shlomo
    Gonzalo, Julio
    Hawking, David
    Jarvelin, Kalervo
    Jones, Gareth
    Jones, Rosie
    Kamps, Jaap
    Kando, Noriko
    Kanoulas, Evangelos
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kelly, Diane
    Lease, Matthew
    Lin, Jimmy
    Mizzaro, Stefano
    Moffat, Alistair
    Murdock, Vanessa
    Oard, Douglas W.
    Rijke, Maarten de
    Sakai, Tetsuya
    Sanderson, Mark
    Scholer, Falk
    Si, Luo
    Thom, James A.
    Thomas, Paul
    Trotman, Andrew
    Turpin, Andrew
    Vries, Arjen P. de
    Webber, William
    Zhang, Xiuzhen (Jenny)
    Zhang, Yi
    Frontiers, Challenges, and Opportunities for Information Retrieval – Report from SWIRL 2012, The Second Strategic Workshop on Information Retrieval in Lorne2012In: SIGIR Forum, ISSN 0163-5840, Vol. 46, no 1, p. 2-32Article in journal (Refereed)
    Abstract [en]

    During a three-day workshop in February 2012, 45 Information Retrieval researchers met to discuss long-range challenges and opportunities within the field. The result of the workshop is a diverse set of research directions, project ideas, and challenge areas. This report describes the workshop format, provides summaries of broad themes that emerged, includes brief descriptions of all the ideas, and provides detailed discussion of six proposals that were voted "most interesting" by the participants. Key themes include the need to: move beyond ranked lists of documents to support richer dialog and presentation, represent the context of search and searchers, provide richer support for information seeking, enable retrieval of a wide range of structured and unstructured content, and develop new evaluation methodologies.

    Download full text (pdf)
    fulltext
  • 10. Alonso, O.
    et al.
    Kamps, J.
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Gavagai .
    Foreword2014In: ESAIR 2014 - Proceedings of the 7th International Workshop on Exploiting Semantic Annotations in Information Retrieval, co-located with CIKM 2014, Association for Computing Machinery (ACM), 2014Conference paper (Refereed)
  • 11. Alonso, O.a
    et al.
    Kamps, J.b
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Seventh workshop on exploiting semantic annotations in information retrieval (ESAIR’14)2014In: CIKM 2014 - Proceedings of the 2014 ACM International Conference on Information and Knowledge Management, Association for Computing Machinery (ACM), 2014, p. 2094-2095Conference paper (Refereed)
    Abstract [en]

    There is an increasing amount of structure on the Web as a result of modern Web languages, user tagging and annotation, emerging robust NLP tools, and an ever growing volume of linked data. These meaningful, semantic, annotations hold the promise to significantly enhance information access, by enhancing the depth of analysis of today’s systems. The goal of the ESAIR’14 workshop remains to advance the general research agenda on this core problem, with an explicit focus on one of the most challenging aspects to address in the coming years. The main remaining challenge is on the user’s side-the potential of rich document annotations can only be realized if matched by more articulate queries exploiting these powerful retrieval cues-and a more dynamic approach is emerging by exploiting new forms of query autosuggest. How can the query suggestion paradigm be used to encourage searcher to articulate longer queries, with concepts and relations linking their statement of request to existing semantic models? How do entity results and social network data in "graph search" change the classic division between searchers and information and lead to extreme personalization-are you the query? How to leverage transaction logs and recommendation, and how adaptive should we make the system? What are the privacy ramifications and the UX aspects-how to not creep out users?

  • 12. Alonso, Omar
    et al.
    Kamps, Jaap
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Report on the Fourth Workshop on Exploiting Semantic Annotations in Information Retrieval (ESAIR 11)2012In: SIGIR Forum, ISSN 0163-5840, E-ISSN 1558-0229, Vol. 46, no 1, p. 56-64Article in journal (Refereed)
    Abstract [en]

    There is an increasing amount of structure on the Web as a result of modern Web languages, user tagging and annotation, and emerging robust NLP tools. These meaningful, semantic, annotations hold the promise to significantly enhance information access, by increasing the depth of analysis of today’s systems. Currently, we have only started to explore the possibilities and only begun to understand how these valuable semantic cues can be put to fruitful use. The workshop had an interactive format consisting of keynotes, boasters and posters, breakout groups and reports, and a final discussion, which was prolonged into the evening. There was a strong feeling that we made substantial progress. Specifically, each of the breakout groups contributed to our understanding of the way forward. First, annotations and use cases come in many different shapes and forms depending on the domain at hand, but at a higher level there are remarkable commonalities in annotation tools, indexing methods, user interfaces, and general methodology. Second, we got insights in the "exploitation" aspects, leading to a clear separation between the low-level annotations giving context or meaning to small units of information (e.g., NLP, sentiments, entities), and annotations bringing out the structure inherent in the data (e.g., sources, data schemas, document genres). Third, the plan to enrich ClueWeb with various document level (e.g., pagerank and spam scores, but also reading level) and lower level (e.g., named entities or sentiments) annotations was embraced by the workshop as a concrete next step to promote research in semantic annotations.

    Download full text (pdf)
    fulltext
  • 13.
    Alpcan, Tansu
    et al.
    Deutsche Telekom Laboratories, TU Berlin.
    Buchegger, Sonja
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Security Games for Vehicular Networks2011In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 10, no 2, p. 280-290Article in journal (Refereed)
    Abstract [en]

    Vehicular networks (VANETs) can be used to improve transportation security, reliability, and management. This paper investigates security aspects of VANETs within a game-theoretic framework where defensive measures are optimized with respect to threats posed by malicious attackers. The formulations are chosen to be abstract on purpose in order to maximize applicability of the models and solutions to future systems. The security games proposed for vehicular networks take as an input centrality measures computed by mapping the centrality values of the car networks to the underlying road topology. The resulting strategies help locating most valuable or vulnerable points (e.g., against jamming) in vehicular networks. Thus, optimal deployment of traffic control and security infrastructure is investigated both in the static (e.g., fixed roadside units) and dynamic cases (e. g., mobile law enforcement units). Multiple types of security games are studied under varying information availability assumptions for the players, leading to fuzzy game and fictitious play formulations in addition to classical zero-sum games. The effectiveness of the security game solutions is evaluated numerically using realistic simulation data obtained from traffic engineering systems.

  • 14. Alwen, Joël
    et al.
    de Rezende, Susanna F.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Cumulative Space in Black-White Pebbling and Resolution2017In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017Conference paper (Refereed)
    Abstract [en]

    We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.

  • 15. Ambuehl, Christoph
    et al.
    Mastrolilli, Monaldo
    Svensson, Ola
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    INAPPROXIMABILITY RESULTS FOR MAXIMUM EDGE BICLIQUE, MINIMUM LINEAR ARRANGEMENT, AND SPARSEST CUT2011In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 2, p. 567-596Article in journal (Refereed)
    Abstract [en]

    We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption.

  • 16.
    Amighi, Afshin
    et al.
    University of Twente.
    de Carvalho Gomes, Pedro
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huisman, Marieke
    University of Twente.
    Provably Correct Control Flow Graphs from Java Bytecode Programs with Exceptions2016In: International Journal on Software Tools for Technology Transfer, ISSN 1433-2779, E-ISSN 1433-2787, ISSN 1433-2779, Vol. 18, no 6, p. 653-684Article in journal (Refereed)
    Abstract [en]

    We present an algorithm for extracting control flow graphs from Java bytecode that captures normal as well as exceptional control flow. We prove its correctness, in the sense that the behaviour of the extracted control flow graph is a sound over-approximation of the behaviour of the original program. This makes control flow graphs suitable for performing various static analyses, such as model checking of temporal safety properties.Analyzing exceptional control flow for Java bytecode is difficult because of the stack-based nature of the language. We therefore develop the extraction in two stages. In the first, we abstract away from the complications arising from exceptional flows, and relativize the extraction on an oracle that is able to look into the stack and predict the exceptions that can be raised at each instruction. This idealized algorithm provides a specification for concrete extraction algorithms, which have to provide a suitable implementation for the oracle. We prove correctness of the idealized algorithm by means of behavioural simulation.In the second stage, we develop a concrete extraction algorithm that consists of two phases. In the first phase, the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control flow graph is extracted in the second phase. We use this intermediate format because it provides the information needed to implement the oracle, and since it gives rise to more compact graphs. We show that the behaviour of the control flow graph extracted via the intermediate representation is a sound over-approximation of the behaviour of the graph extracted by the direct, idealized algorithm, and thus of the original program. The concrete extraction algorithm is implemented as the ConFlEx tool. A number of test cases are performed to evaluate the efficiency of the algorithm.

  • 17.
    Amighi, Afshin
    et al.
    University of Twente.
    de Carvalho Gomes, Pedro
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huisman, Marieke
    University of Twente.
    Provably Correct Control-Flow Graphs from Java Programs with Exceptions2012Report (Other academic)
    Abstract [en]

    We present an algorithm to extract flow graphs from Java bytecode, including exceptional control flows. We prove its correctness, meaning that the behavior of the extracted control-flow graph is a sound over-approximation of the behavior of the original program. Thus any safety property that holds for the extracted control-flow graph also holds for the original program. This makes control-flow graphs suitable for performing various static analyses, such as model checking.The extraction is performed in two phases. In the first phase the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control-flow graph is extracted in the second phase. We use this intermediate format because it results in compact flow graphs, with provably correct exceptional control flow. To prove the correctness of the two-phase extraction, we also define an idealized extraction algorithm, whose correctness can be proven directly. Then we show that the behavior of the control-flow graph extracted via the intermediate representation is an over-approximation of the behavior of the directly extracted graphs, and thus of the original program. We implemented the indirect extraction as the CFGEx tool and performed several test-cases to show the efficiency of the algorithm.

    Download full text (pdf)
    fulltext
  • 18.
    Amighi, Afshin
    et al.
    University of Twente.
    de Carvalho Gomes, Pedro
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Gurov, Dilian
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huisman, Marieke
    University of Twente.
    Sound Control-Flow Graph Extraction for Java Programs with Exceptions2012In: Software Engineering and Formal Methods: 10th International Conference, SEFM 2012, Thessaloniki, Greece, October 1-5, 2012. Proceedings, Springer Berlin/Heidelberg, 2012, p. 33-47Conference paper (Refereed)
    Abstract [en]

    We present an algorithm to extract control-flow graphs from Java bytecode, considering exceptional flows. We then establish its correctness: the behavior of the extracted graphs is shown to be a sound over-approximation of the behavior of the original programs. Thus, any temporal safety property that holds for the extracted control-flow graph also holds for the original program. This makes the extracted graphs suitable for performing various static analyses, in particular model checking. The extraction proceeds in two phases. First, we translate Java bytecode into BIR, a stack-less intermediate representation. The BIR transformation is developed as a module of Sawja, a novel static analysis framework for Java bytecode. Besides Sawja’s efficiency, the resulting intermediate representation is more compact than the original bytecode and provides an explicit representation of exceptions. These features make BIR a natural starting point for sound control-flow graph extraction. Next, we formally define the transformation from BIR to control-flow graphs, which (among other features) considers the propagation of uncaught exceptions within method calls. We prove the correctness of the two-phase extraction by suitably combining the properties of the two transformations with those of an idealized control-flow graph extraction algorithm, whose correctness has been proved directly. The control-flow graph extraction algorithm is implemented in the ConFlEx tool. A number of test-cases show the efficiency and the utility of the implementation.

  • 19. Amighi, Afshin
    et al.
    de Carvalho Gomes, Pedro
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huisman, Marieke
    Provably Correct Control-Flow Graphs from Java Programs with Exceptions2011In: Formal Verification of Object-Oriented Software, 2011, Vol. 26, p. 31-48Conference paper (Refereed)
    Abstract [en]

    We present an algorithm to extract flow graphs from Java bytecode, focusing on exceptional control flows. We prove its correctness, meaning that the behaviour of the extracted control-flow graph is an over-approximation of the behaviour of the original program. Thus any safety property that holds for the extracted control-flow graph also holds for the original program. This makes control-flow graphs suitable for performing different static analyses. For precision and efficiency, the extraction is performed in two phases. In the first phase the program is transformed into a BIR program, where BIR is a stack-less intermediate representation of Java bytecode; in the second phase the control-flow graph is extracted from the BIR representation. To prove the correctness of the two-phase extraction, we also define a direct extraction algorithm, whose correctness can be proven immediately. Then we show that the behaviour of the control-flow graph extracted via the intermediate representation is an over-approximation of the behaviour of the directly extracted graphs, and thus of the original program.

  • 20. Amundin, Mats
    et al.
    Eklund, Robert
    Hållsten, Henrik
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Molinder, Lars
    A proposal to use distributional models to analyse dolphin vocalization2017In: 1st International Workshop on Vocal Interactivity in-and-between Humans, Animals and Robots, 2017, 2017Conference paper (Refereed)
    Abstract [en]

    This paper gives a brief introduction to the starting points of an experimental project to study dolphin communicative behaviour using distributional semantics, with methods implemented for the large scale study of human language.

    Download full text (pdf)
    fulltext
  • 21. Andersdotter, Amelia
    et al.
    Bylund, Markus
    Ferm, Maria
    Häglund, Kjell
    Jardenberg, Joakim
    de Kaminski, Marcin
    Karlberg, Peter
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Larsson, Hanna
    Sundberg, Sam
    Sundin, Mathias
    Godtyckligt regelverk hotar friheten på nätet2013In: Dagens Nyheter, ISSN 1101-2447, no 2013-09-03Article in journal (Other (popular science, discussion, etc.))
    Abstract [sv]

    Reglerna som möjliggör stängning av hemsidor på internet präglas av godtycke och otydlighet. Men det behöver inte vara särskilt svårt att skapa ett nytt och rättssäkert regelverk. Här har Sveriges EU-kommissionär Cecilia Malmström en viktig roll. Frågan är om hon tar sitt ansvar, skriver politiker och nätdebattörer.

  • 22. Andersson-Schwarz, Jonas
    et al.
    Christensen, Christian
    Eellend, Beate
    Hadley Kamptz, Isobel
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Thorslund, Ewa
    Wormbs, Nina
    KTH, School of Architecture and the Built Environment (ABE), Philosophy and History, History of Science, Technology and Environment.
    Transaktionsdimman på nätet hotar digitaliseringen2017In: Dagens Nyheter, ISSN 1101-2447Article in journal (Other (popular science, discussion, etc.))
    Abstract [sv]

    På nätet är vi inte längre bara medborgare eller kunder. Vi är också varor. De data vi läm-nar ut om oss själva är vad andra tjänar pengar på. Men vi vet inte vad de är värda ochvad vi skulle kunna begära i betalning. Transaktionsdimman på internet bör skingrasoch ersättas av transaktionstransparens, skriver sju medie- och it-debattörer.

  • 23. Ansotegui, Carlos
    et al.
    Luisa Bonet, Maria
    Giraldez-Cru, Jesus
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Spanish National Research Council, Spain.
    Levy, Jordi
    Structure features for SAT instances classification2017In: Journal of Applied Logic, ISSN 1570-8683, E-ISSN 1570-8691, Vol. 23, p. 27-39Article in journal (Refereed)
    Abstract [en]

    The success of portfolio approaches in SAT solving relies on the observation that different SAT solvers may dramatically change their performance depending on the class of SAT instances they are trying to solve. In these approaches, a set of features of the problem is used to build a prediction model, which classifies instances into classes, and computes the fastest algorithm to solve each of them. Therefore, the set of features used to build these classifiers plays a crucial role. Traditionally, portfolio SAT solvers include features about the structure of the problem and its hardness. Recently, there have been some attempts to better characterize the structure of industrial SAT instances. In this paper, we use some structure features of industrial SAT instances to build some classifiers of industrial SAT families of instances. Namely, they are the scale-free structure, the community structure and the self similar structure. First, we measure the effectiveness of these classifiers by comparing them to other sets of SAT features commonly used in portfolio SAT solving approaches. Then, we evaluate the performance of this set of structure features when used in a real portfolio SAT solver. Finally, we analyze the relevance of these features on the analyzed classifiers.

  • 24. Argaw, A. A.
    et al.
    Asker, L.
    Cöster, R.
    Karlgren, Jussi
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Dictionary based Amharic - English information retrieval2004In: CEUR Workshop Proceedings, CEUR-WS , 2004Conference paper (Refereed)
    Abstract [en]

    We present two approaches to the Amharic - English bilingual track in CLEF 2004. Both experiments use a dictionary based approach to translate the Amharic queries into English Bags-of-words, but while one approach removes non-content bearing words from the Amharic queries based on their IDF value, the other uses a list of English stop words to perform the same task. The resulting translated (English) terms are then submitted to a retrieval engine that supports the Boolean and vector-space models. In our experiments, the second approach (based on a list of English stop words) performs slightly better than the one based on IDF values for the Amharic terms.

  • 25.
    Artho, Cyrille
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Olveczky, Peter Csaba
    Formal Techniques for Safety-Critical Systems (FTSCS 2014) Preface2017In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 133, p. 89-90Article in journal (Other academic)
  • 26. Atserias, A.
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow proofs may be maximally long2014In: Proceedings of the Annual IEEE Conference on Computational Complexity, 2014, p. 286-297Conference paper (Refereed)
    Abstract [en]

    We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size nω(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size nO(ω) is essentially tight. Moreover, our lower bounds can be generalized to polynomial calculus resolution (PCR) and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. Our results do not extend all the way to Lasserre, however-the formulas we study have Lasserre proofs of constant rank and size polynomial in both n and w.

  • 27. Atserias, Albert
    et al.
    Lauria, Massimo
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow Proofs May Be Maximally Long2016In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 17, no 3, article id 19Article in journal (Refereed)
    Abstract [en]

    We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n(Omega(w)). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n(O(w)) is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w.

  • 28. Austrin, P.
    et al.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the usefulness of predicates2012In: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), IEEE , 2012, p. 53-63Conference paper (Refereed)
    Abstract [en]

    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.

  • 29.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Balanced Max 2-Sat Might Not be the Hardest: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING2007In: STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, New York: ASSOC COMPUTING MACHINERY, , 2007, p. 189-197Conference paper (Refereed)
    Abstract [en]

    We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX 2-SAT within alpha(-)(L)(LZ)+epsilon where 0.9401 < alpha(-)(L)(LZ) < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick [28].. This result is surprising considering the fact that balanced instances of MAX 2-SAT, i.e., instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. In particular, instances in which roughly 68% of the literals are unnegated variables and 32% are negated appear less amenable to approximation than instances where the ratio is 50%-50%.

  • 30.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Conditional Inapproximability and Limited Independence2008Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. These are problems in which we are given a set of constraints, each constraint acting on some k variables, and are asked to find an assignment to the variables satisfyingas many of the constraints as possible.

    A predicate P : [q]ᵏ → {0, 1} is said to be approximation resistant if it is intractable to approximate the corresponding CSP problem to within a factor which is better than what is expected from a completely random assignment to the variables. We prove that if the Unique Games Conjecture is true, then a sufficient condition for a predicate P :[q]ᵏ → {0, 1} to be approximation resistant is that there exists a pairwise independent distribution over [q]ᵏ which is supported on the set of satisfying assignments Pˉ¹(1) of P.

    We also study predicates P : {0, 1}² → {0, 1} on two boolean variables. The corresponding CSP problems include fundamental computational problems such as Max Cut and Max 2-Sat. For any P, we give an algorithm and a Unique Games-based hardness result. Under a certain geometric conjecture, the ratios of these two results are shown to match exactly. In addition, this result explains why additional constraints beyond the standard “triangle inequalities” do not appear to help when solving these problems. Furthermore,we are able to use the generic hardness result to obtain improved hardness for the special cases of Max 2-Sat and Max 2-And. For Max 2-Sat, we obtain a hardness of αLLZ + ε ≈ 0.94016, where αLLZ is the approximation ratio of the algorithm due to Lewin, Livnat and Zwick. For Max 2-And, we obtain a hardness of 0.87435. For both of these problems, our results surprisingly demonstrate that the special case of balanced instances (instances where every variable occurs positively and negatively equally often) is not the hardest. Furthermore, the result for Max 2-And also shows that Max Cut is not the hardest 2-CSP.

    Motivated by the result for k-CSP problems, and their fundamental importance in computer science in general, we then study t-wise independent distributions with random support. We prove that, with high probability, poly(q) ・ n² random points in [q]ⁿ can support a pairwise independent distribution. Then, again with high probability, we show that (poly(q) ・n)ᵗ log(nᵗ) random points in [q]ⁿ can support a t-wise independent distribution. For constant t and q, we show that Ω(nᵗ) random points are necessary in order to be able to support a t-wise independent balanced distribution with non-negligible probability. Also, we show that every subset of [q]ⁿ with size at least qⁿ(1−poly(q)ˉᵗ) can support a t-wise independent distribution.

    Finally, we prove a certain noise correlation bound for low-degree functions with small Fourier coefficients. This type of result is generally useful in hardness of approximation, derandomization, and additive combinatorics.

    Download full text (pdf)
    Full Text
  • 31.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Towards sharp inapproximability for any 2-CSP2007In: 48th Annual IEEE Symposium On Foundations Of Computer Science, Proceedings, 2007, p. 307-317Conference paper (Refereed)
    Abstract [en]

    We continue the recent line, of work on the connection between semidefinite programming-based approximation algorithms and the Unique Games Conjecture. Given any boolean 2-CSP (or more generally, any nonnegative objective function on two boolean variables), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. The key objects in our analysis are the vector triples arising when doing clause-by-clause analysis of algorithms based on semidefinite programming. Given a. weighted set of such triples of a certain restricted type, which are "hard" to round in a certain sense, we obtain a Unique Games-based inapproximability matching this "hardness" of rounding the set of vector triples. Conversely, any instance together with an SDP solution can be viewed as a set of vector triples, and we show that we can always find an assignment to the instance which is at least as good as the "hardness" of rounding the corresponding set of vector triples. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that MAX 2-AND is hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856, and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of MAX 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor alpha(GW).

  • 32.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    TOWARDS SHARP INAPPROXIMABILITY FOR ANY 2-CSP2010In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 39, no 6, p. 2430-2463Article in journal (Refereed)
    Abstract [en]

    We continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued "predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-AND is unique games-hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856 and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of Max 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor aGW and that Max Cut is not the hardest 2-CSP.

  • 33.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Benabbas, S.
    Georgiou, K.
    Better balance by being biased: A 0.8776-approximation for max bisection2013In: Proc Annu ACM SIAM Symp Discrete Algorithms, 2013, p. 277-294Conference paper (Refereed)
    Abstract [en]

    Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the MAX BISECTION problem. We improve their algorithm to a 0.8776-approximation. As MAX BISECTION is hard to approximate within αGW + ∈ ≈ 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within αGW -∈, i.e., the bisection constraint (essentially) does not make MAX CUT harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of MAX 2-SAT. Our approximation ratio for this problem exactly matches the optimal approximation ratio for MAX 2-SAT, i.e., αLLZ + ∈ ≈ 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.

  • 34.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Benabbas, Siavosh
    Georgiou, Konstantinos
    Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection2016In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 1, article id 2Article in journal (Refereed)
    Abstract [en]

    Recently, Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the MAX BISECTION problem. We improve their algorithm to a 0.8776-approximation. As MAX BISECTION is hard to approximate within alpha(GW) + epsilon approximate to 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within alpha(GW) - epsilon, that is, that the bisection constraint (essentially) does not make MAX CUT harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of MAX 2-SAT. Our approximation ratio for this problem exactly matches the optimal approximation ratio for MAX 2-SAT, that is, alpha(LLZ) + epsilon approximate to 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem from Raghavendra and Tan.

  • 35.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Chung, K. -M
    Mahmoody, M.
    Pass, R.
    Seth, K.
    On the impossibility of cryptography with tamperable randomness2014In: 34rd Annual International Cryptology Conference, CRYPTO 2014, Springer Berlin/Heidelberg, 2014, no PART 1, p. 462-479Conference paper (Refereed)
    Abstract [en]

    We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may efficiently tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. Our main result is a strong negative result: We show that any secure encryption scheme, bit commitment scheme, or zero-knowledge protocol can be "broken" with probability p by a p-tampering attacker.The core of this result is a new Fourier analytic technique for biasing the output of bounded-value functions, which may be of independent interest. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (1/poly(n))- tampering attacks where n is the security parameter.

  • 36.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Chung, Kai-Min
    Mahmoody, Mohammad
    Pass, Rafael
    Seth, Karn
    On the Impossibility of Cryptography with Tamperable Randomness2017In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 79, no 4, p. 1052-1101Article in journal (Refereed)
    Abstract [en]

    We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may efficiently tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. Our main result is a strong negative result: We show that any secure encryption scheme, bit commitment scheme, or zero-knowledge protocol can be "broken" with advantage Omega(p) by a p-tampering attacker. The core of this result is a new algorithm for biasing the output of bounded-value functions, which may be of independent interest. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (1/poly(n))-tampering attacks where n is the security parameter.

  • 37.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Guruswami, V.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    (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]

    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.

  • 38.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the Usefulness of Predicates2012In: ACM Transactions on Computation Theory, ISSN 19423454, Vol. 5, no 1Article in journal (Refereed)
    Abstract [en]

    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.

  • 39.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Univ Toronto, Dept Comp Sci.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    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]

    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.

  • 40.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    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]

    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.

  • 41.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Guruswami, V.
    (2 + epsilon)-Sat Is NP-hard2014In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, p. 1-10Conference paper (Refereed)
    Abstract [en]

    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 &amp;epsi; > 0, the hardness of finding a satisfyingassignment to instances of '(2 + &amp;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.

  • 42.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Pass, R.
    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]

    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 &lt; 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 &lt; 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 + ∈.

  • 43.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Aalto Science Institute, Aalto University, Finland .
    Kaski, P.
    Koivisto, M.
    Määttä, J.
    Space-time tradeoffs for subset sum: An improved worst case algorithm2013In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, p. 45-56Conference paper (Refereed)
    Abstract [en]

    The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the Subset Sum problem. In the random-instance setting, however, improved tradeoffs exist. In particular, the recently discovered dissection method of Dinur et al. (CRYPTO 2012) yields a significantly improved space-time tradeoff curve for instances with strong randomness properties. Our main result is that these strong randomness assumptions can be removed, obtaining the same space-time tradeoffs in the worst case. We also show that for small space usage the dissection algorithm can be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space-time controls into the algorithm by means of a "bailout mechanism".

  • 44.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlof, J.
    Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs2016In: 2016 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers (IEEE), 2016, Vol. 2016, p. 335-339, article id 7541316Conference paper (Refereed)
    Abstract [en]

    Two sets A, B subset of {0, 1}(n) form a Uniquely Decodable Code Pair (UDCP) if every pair a is an element of A, b is an element of B yields a distinct sum a + b, where the addition is over Z(n). We show that every UDCP A, B, with vertical bar A vertical bar = 2((1-is an element of)n) and vertical bar B vertical bar = 2(beta n), satisfies beta <= 0.4228 + root is an element of. For sufficiently small is an element of, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop '98] and Ordentlich and Shayevitz [2014, arXiv: 1412.8415], which upper bound beta by 0.4921 and 0.4798, respectively, as is an element of approaches 0.

  • 45.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlof, J.
    Subset sum in the absence of concentration2015In: Leibniz International Proceedings in Informatics, LIPIcs, 2015, p. 48-61Conference paper (Refereed)
    Abstract [en]

    We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O (20.3399nB4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.

  • 46.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlöf, J.
    Dense Subset Sum may be the hardest2016In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)
    Abstract [en]

    The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5-δ)n)-time algorithm, with some constant δ &gt; 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ &gt; 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

  • 47.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, S.
    A characterization of approximation resistance for even k-partite CSPs2013In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, p. 187-196Conference paper (Refereed)
    Abstract [en]

    A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.

  • 48.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem2014In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 60, no 10, p. 6636-6645Article in journal (Refereed)
    Abstract [en]

    We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over F-2. We also show how to extend the reduction to work over any fixed finite field. Previously, a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes.

  • 49.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    Safra, Muli
    Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs2009In: PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, p. 74-80Conference paper (Refereed)
    Abstract [en]

    We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + O-d (1)) log logd/log d. This exactly matches the algorithmic result of Halperin [1] up to the O-d(1) term. Independent Set is Unique Games-hard to approximate to within a factor O(d/log(2)d). This improves the d/log(O(1)) (d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].

  • 50.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    Safra, Muli
    Inapproximability of vertex cover and independent set in bounded degree graphs2011In: Theory of Computing, E-ISSN 1557-2862, Vol. 7, p. 27-43Article in journal (Refereed)
1234567 1 - 50 of 518
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf